Paper by Erik D. Demaine
- Mihai Bădoiu, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Piotr Indyk, “Low-Dimensional Embedding with Extra Information”, Discrete & Computational Geometry, volume 36, number 4, December 2006, pages 609–632. Special issue of selected papers from the 20th Annual ACM Symposium on Computational Geometry.
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 two-dimensional coordinates to the vertices such that the
(multiplicative or additive) error on the resulting distances and other
information is within a constant factor of the best possible. We obtain the
first pseudo-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
pseudo-quasipolynomial-time algorithm for no extra information can also be
viewed as a polynomial-time algorithm given an “extremum oracle”
as extra information. We give several approximation algorithms and
contrasting hardness results for these scenarios.
- This paper is also available from SpringerLink.
- The paper is 22 pages.
- The paper is available in PostScript (586k), gzipped PostScript (225k), and PDF (334k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Embedding_SoCG2004 (Low-Dimensional Embedding with Extra Information)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated April 22, 2019 by