Low-dimensional embedding with extra information

ABSTRACT

A frequently arising problem in computational geometry is when a physical structure, such as an ad-hoc wireless sensor network or a protein backbone, can measure local information about its geometry (e.g., distances, angles, and/or orientations), and the goal is to reconstruct the global geometry from this partial information. More precisely, we are given a graph, the approximate lengths of the edges, and possibly extra information, and our goal is to assign coordinates to the vertices that satisfy the given constraints up to a constant factor away from the best possible. We obtain the first subexponential-time (quasipolynomial-time) algorithm for this problem given a complete graph of Euclidean distances with additive error and no extra information. For general graphs, the analogous problem is NP-hard even with exact distances. Thus, for general graphs, we consider natural types of extra information that make the problem more tractable, including approximate angles between edges, the order type of vertices, a model of coordinate noise, or knowledge about the range of distance measurements. Our quasipolynomial-time algorithm for no extra information can also beviewed as a polynomial-time algorithm given an "extremum oracle" as extra information. We give several approximation algorithms and contrasting hardness results for these scenarios.

REFERENCES

• 1: Richa Agarwala , Vineet Bafna , Martin Farach , Babu Narayanan , Mike Paterson , Mikkel Thorup, On the approximability of numerical taxonomy (fitting distances by tree metrics), Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.365-372, January 28-30, 1996, Atlanta, Georgia, United States
• 2: Bonnie Berger , Jon Kleinberg , Tom Leighton, Reconstructing a three-dimensional model with arbitrary errors, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.449-458, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237993]
• 3: Mihai Bâdoiu, Approximation algorithm for embedding metrics into a two-dimensional space, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 4: S. Capkun , M. Hamdi , J. Hubaux, GPS-Free Positioning in Mobile ad-hoc Networks, Proceedings of the 34th Annual Hawaii International Conference on System Sciences ( HICSS-34)-Volume 9, p.9008, January 03-06, 2001
• 5: R. CONNELLY, On generic global rigidity, in Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, P. Gritzman and B. Sturmfels, eds., vol. 4 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS Press, 1991, pp. 147--155.
• 6: C. COULLARD AND A. LUBIW, Distance visibility graphs, Internat. J. Comput. Geom. Appl., 2 (1992), pp. 349--362.
• 7: G. M. CRIPPEN AND T. F. HAVEL, Distance Geometry and Molecular Conformation, John Wiley & Sons, 1988.
• 8: H. EVERETT, C. T. HOÀNG, K. KILAKOS, AND M. NOY, Distance segment visibility graphs. Manuscript, 1999. http://www.loria.fr/.everett/publications/distance.html.
• 9: Martin Farach , Sampath Kannan, Efficient algorithms for inverting evolution, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.230-236, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237868]
• 10: Johan Håstad , Lars Ivansson , Jens Lagergren, Fitting Points on the Real Line and Its Application to RH Mapping, Proceedings of the 6th Annual European Symposium on Algorithms, p.465-476, August 24-26, 1998
• 11: Bruce Hendrickson, Conditions for unique graph realizations, SIAM Journal on Computing, v.21 n.1, p.65-84, Feb. 1992 [doi>10.1137/0221008]
• 12: ---, The molecule problem: Exploiting structure in global optimization, SIAM J. on Optimization, 5 (1995), pp. 835--857.
• 13: L. IVANSSON, Computational aspects of radiation hybrid, Doctoral Dissertation, Department of Numerical Analysis and Computer Science, Royal Institute of Technology, (2000).
• 14: B. JACKSON AND T. JORDÁN, Connected rigidity matroids and unique realizations of graphs. Manuscript, March 2003.
• 15: J. KRUSKAL, Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis, Psychometrika, 29 (1964), pp. 1--27.
• 16: ---, Nonmetric multidimensional scaling: A numerical method, Psychometrika, 29 (1964), pp. 115--129.
• 17: Nissanka B. Priyantha , Anit Chakraborty , Hari Balakrishnan, The Cricket location-support system, Proceedings of the 6th annual international conference on Mobile computing and networking, p.32-43, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345917]
• 18: Nissanka B. Priyantha , Allen K.L. Miu , Hari Balakrishnan , Seth Teller, The cricket compass for context-aware mobile applications, Proceedings of the 7th annual international conference on Mobile computing and networking, p.1-14, July 2001, Rome, Italy [doi>10.1145/381677.381679]
• 19: C. SAVARESE, J. RABAEY, AND J. BEUTEL, Locationing in distributed ad-hoc wireless sensor networks, in Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, Salt Lake City, UT, May 2001, pp. 2037--2040.
• 20: J. B. SAXE, Embeddability of weighted graphs in k-space is strongly NP-hard, in Proc. 17th Allerton Conf. Commun. Control Comput., 1979, pp. 480--489.
• 21: J. B. SAXE, Two papers on graph embedding problems, Tech. Rep. CMU-CS-80-102, Department of Computer Science, Carnegie-Mellon University, Jan. 1980.
• 22: R. N. SHEPARD, The analysis of proximities: Multidimensional scaling with an unknown distance function 1, Psychometrika, 27 (1962), pp. 125--140.
• 23: ---, The analysis of proximities: Multidimensional scaling with an unknown distance function 2, Psychometrika, 27 (1962), pp. 216--246.
• 24: WORKING GROUP ON ALGORITHMS FOR MULTIDIMENSIONAL SCALING, Algorithms for multidimensional scaling. http://dimacs.rutgers.edu/SpecialYears/2001_Data/Algorithms/MDSdescription.html.
• 25: Y. YEMINI, Some theoretical aspects of positionlocation problems, in Proc. 20th Annu. IEEE Sympos. Found. Comput. Sci., 1979, pp. 1--8.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
angles, approximation algorithms, distribution, graph embedding, metrics, order type, range graphs