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 > >