Paper by Erik D. Demaine
- Mihai Bădoiu, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Piotr Indyk, “Low-Dimensional Embedding with Extra Information”, in Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004), Brooklyn, New York, June 9–11, 2004, pages 320–329.
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 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 the ACM Digital Library.
- The paper is 10 pages.
- The paper is available in PostScript (1032k), gzipped PostScript (541k), and PDF (222k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Embedding_DCG (Low-Dimensional Embedding with Extra Information)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated June 27, 2019 by