Re: connectivity matrix.
- To: mathgroup at smc.vnet.net
- Subject: [mg28667] Re: [mg28646] connectivity matrix.
- From: "Mark Harder" <harderm at ucs.orst.edu>
- Date: Sat, 5 May 2001 04:00:51 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Pete,
All I can offer are some insights I think I have.
What you are trying to accomplish is solve a kind of inverse problem:
given absolute spatial locations of a set of points, it is easy to compute
their relative distances (the forward problem), but computing absolute
locations from a set of distances is messier, especially if you don't know
*all* the inter-point distances. What fascinates me about your query is its
application to swarms: I know of it as an application to solving molecular
structures (absolute locations of all atoms in a molecule in some 3-space
coordinate system) from experiments that yield only a subset of all
distances between atoms. The technique of NuclearMagneticResonance (NMR) is
the prime example of this, since all it computes is inter-atom distances,
which then have to be transformed into the locations of the atoms in the
molecule under study.
The body of theory & application that I think you can use to solve your
problem is sometimes called Distance Geometry -- the study of classes of
point sets that are equivalent in that they all have the same matrix of
distances, and the symmetries possessed by these classes. For eg. ,a
tetrahedron with a complete distance matrix is mirror-symmetry related to
another tetrahedron, not necessarily superimposable on the first, with an
identical distance matrix. ( Remember your college organic chemistry and its
explanation of "chiral" molecules based on the tetrahedral structure of
"asymmetric" carbon compounds?)
So, I suggest that you search on the term "distance geometry". Also,
there are 2 books by Gordon Crippen with "Distance Geometry ......." titles
that concern themselves with applications to molecular conformation and
structure.
-mark harder
-----Original Message-----
From: Pete Bielawski <peteb at cisco.com>
To: mathgroup at smc.vnet.net
Subject: [mg28667] [mg28646] connectivity matrix.
>i'm trying to come up with an algorithm for transforming a matrix of
>relative distances(A is 2 units from B, 3 units from C, 9 units from D,
>B is 2 units from A, 1 unit from C, 11 units from D, etc...) to a matrix
>describing the locations of the points on some arbitrary axis(A is
>(0,0,0), B is (2,0,0), C is (6,2,2), etc...). this algorithm is related
>to swarm theory in some ways - trying to get a system of 100+ nodes
>moving as one, for example.
>
>so far, i've tried several methods: angle matching, applying similar
>triangles, intersecting spheres, using polar coordinates instead, etc.,
>but all of them seem to require excessive iteration and search trees.
>i'm not asking for someone to solve my problem - i'm just looking for a
>link that might help.
>
>thanks in advance!
>
>P
>
>