More Web Proxy on the site http://driver.im/

Article

Low-dimensional embedding with extra information

Authors:

Erik D. Demaine,

Mohammad Taghi Hajiaghayi,

Piotr IndykAuthors Info & Claims

SCG '04: Proceedings of the twentieth annual symposium on Computational geometry

Pages 320 - 329

https://doi.org/10.1145/997817.997866

Published: 08 June 2004 Publication History

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]

R. AGARWALA, V. BAFNA, M. FARACH-COLTON, B. NARAYANAN, M. PATERSON, AND M. THORUP, On the approximability of numerical taxonomy: (fitting distances by tree metrics), 7th Symposium on Discrete Algorithms, (1996).]]

Digital Library

[2]

B. BERGER,J.KLEINBERG, AND T. LEIGHTON, Reconstructing a three-dimensional model with arbitrary errors, in Proc. 28th Annu. ACMSympos. Theory Comput., May 1996, pp. 449--458.]]

Digital Library

[3]

M. BǍDOIU, Approximation algorithm for embedding metrics into a two-dimensional space, 14th Annual ACM-SIAM Symposium on Discrete Algorithms, (2003).]]

Digital Library

[4]

S. CAPKUN, M. HAMDI, AND J.-P. HUBAUX, Gps-free positioning in mobile ad-hoc networks, in Proceedings of the 34th Hawaii International Conference on System Sciences, January 2001, pp. 3481--3490.]]

Digital Library

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

M. FARACH-COLTON AND S. KANNAN, Efficient algorithms for inverting evolution, 28th Symposium on Theory of Computing, (1996).]]

Digital Library

[10]

J. HASTAD,L.IVANSSON, AND J. LAGERGREN, Fitting points on the real line and its application to rh mapping, Lecture Notes in Computer Science, 1461 (1998), pp. 465--467.]]

Digital Library

[11]

B. HENDRICKSON, Conditions for unique graph realizations, SIAM J. Comput., 21 (1992), pp. 65--84.]]

Digital Library

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

N. B. PRIYANTHA, A.CHAKRABORTY, AND H. BALAKR-ISHNAN, The Cricket location-support system, in Proceedings of 6th Annual International Conference on Mobile Computing and Networking, Boston, MA, August 2000, pp. 32--43.]]

Digital Library

[18]

N. B. PRIYANTHA, A. K. L. MIU, H. BALAKRISHNAN, AND S. TELLER, The Cricket compass for context-aware mobile applications, in Proceedings of the 7th ACM International Conference on Mobile Computing and Networking, Rome, Italy, July 2001, pp. 1--14.]]

Digital Library

[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.]]

Cited By

Liu YYang ZLiu YYang Z(2024)Error ControlLocation, Localization, and Localizability10.1007/978-981-97-3176-3_6(85-109)Online publication date: 12-Jul-2024
https://doi.org/10.1007/978-981-97-3176-3_6
Yang ZJian LWu CLiu Y(2013)Beyond triangle inequalityACM Transactions on Sensor Networks10.1145/2422966.24229839:2(1-20)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1145/2422966.2422983
Jian LYang ZLiu Y(2010)Beyond triangle inequalityProceedings of the 29th conference on Information communications10.5555/1833515.1833781(1972-1980)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.5555/1833515.1833781
Show More Cited By

Index Terms

Low-dimensional embedding with extra information
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Low-Dimensional Embedding with Extra Information

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 ...
Embedding into Bipartite Graphs

The conjecture of Bollobás and Komlós, recently proved by Böttcher, Schacht, and Taraz [Math. Ann., 343 (2009), pp. 175-205], implies that for any $\gamma>0$, every balanced bipartite graph on $2n$ vertices with bounded degree and sublinear bandwidth ...
Embedding and canonizing graphs of bounded genus in logspace
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

Graph embeddings of bounded Euler genus (that means, embeddings with bounded orientable or nonorientable genus) help to design time-efficient algorithms for many graph problems. Since linear-time algorithms are known to compute embeddings of any bounded ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '04: Proceedings of the twentieth annual symposium on Computational geometry

June 2004

468 pages

ISBN:1581138857

DOI:10.1145/997817

Conference Chairs:
Jack Snoeyink
UNC Chapel Hill
,
Jean-Daniel Boissonnat
INRIA Sophia Antipolis

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 June 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SoCG04

Sponsor:

SoCG04: Annual ACM Symposium on Computational Geometry 2004

June 8 - 11, 2004

New York, Brooklyn, USA

Acceptance Rates

SCG '04 Paper Acceptance Rate 49 of 147 submissions, 33%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
376
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu YYang ZLiu YYang Z(2024)Error ControlLocation, Localization, and Localizability10.1007/978-981-97-3176-3_6(85-109)Online publication date: 12-Jul-2024
https://doi.org/10.1007/978-981-97-3176-3_6
Yang ZJian LWu CLiu Y(2013)Beyond triangle inequalityACM Transactions on Sensor Networks10.1145/2422966.24229839:2(1-20)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1145/2422966.2422983
Jian LYang ZLiu Y(2010)Beyond triangle inequalityProceedings of the 29th conference on Information communications10.5555/1833515.1833781(1972-1980)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.5555/1833515.1833781
Jian LYang ZLiu Y(2010)Beyond Triangle Inequality: Sifting Noisy and Outlier Distance Measurements for Localization2010 Proceedings IEEE INFOCOM10.1109/INFCOM.2010.5462019(1-9)Online publication date: Mar-2010
https://doi.org/10.1109/INFCOM.2010.5462019
Akcan HKriakov VBrönnimann HDelis A(2010)Managing cohort movement of mobile sensors via GPS-free and compass-free node localizationJournal of Parallel and Distributed Computing10.1016/j.jpdc.2010.03.00770:7(743-757)Online publication date: 1-Jul-2010
https://dl.acm.org/doi/10.1016/j.jpdc.2010.03.007
Das SWang JGhosh RReiger R(2010)Algorithmic Aspects of Sensor LocalizationTheoretical Aspects of Distributed Computing in Sensor Networks10.1007/978-3-642-14849-1_9(257-291)Online publication date: 8-Nov-2010
https://doi.org/10.1007/978-3-642-14849-1_9
Lederer SWang YGao J(2009)Connectivity-based localization of large-scale sensor networks with complex shapeACM Transactions on Sensor Networks10.1145/1614379.16143835:4(1-32)Online publication date: 27-Nov-2009
https://dl.acm.org/doi/10.1145/1614379.1614383
Bruck JGao JJiang A(2009)Localization and routing in sensor networks by local angle informationACM Transactions on Sensor Networks10.1145/1464420.14644275:1(1-31)Online publication date: 11-Feb-2009
https://dl.acm.org/doi/10.1145/1464420.1464427
Kulis BJain PGrauman K(2009)Fast Similarity Search for Learned MetricsIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2009.15131:12(2143-2157)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1109/TPAMI.2009.151
Wang YLederer SGao J(2009)Connectivity-Based Sensor Network Localization with Incremental Delaunay Refinement MethodIEEE INFOCOM 2009 - The 28th Conference on Computer Communications10.1109/INFCOM.2009.5062167(2401-2409)Online publication date: Apr-2009
https://doi.org/10.1109/INFCOM.2009.5062167
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents