Low-Dimensional Embedding with Extra Information |
| |
Authors: | Mihai Badoiu Erik D Demaine MohammadTaghi Hajiaghayi Piotr Indyk |
| |
Institution: | (1) Computer Science and Artificial Intelligence Laboratory, MIT, 32 Vassar Street, Cambridge, MA 02139, USA |
| |
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 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|