NDLI: Low-Dimensional Embedding with Extra Information

Content Provider	Springer Nature Link
Author	Badoiu, Mihai Demaine, Erik D. Hajiaghayi, MohammadTaghi Indyk, Piotr
Copyright Year	2006
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.
Starting Page	609
Ending Page	632
Page Count	24
File Format	PDF
ISSN	01795376
Journal	Discrete & Computational Geometry
Volume Number	36
Issue Number	4
e-ISSN	14320444
Language	English
Publisher	Springer-Verlag
Publisher Date	2006-10-18
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Computational Mathematics and Numerical Analysis Combinatorics
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Theoretical Computer Science Computational Theory and Mathematics Geometry and Topology

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Low-Dimensional Embedding with Extra Information

Embedding Tree Metrics into Low-Dimensional Euclidean Spaces

Consistent Digital Rays

Volume in General Metric Spaces

Four-Dimensional Regular Polyhedra

Grid Embedding of 4-Connected Plane Graphs

Three-Dimensional Delaunay Mesh Generation

Linkless and Flat Embeddings in 3-Space

Some Low Distortion Metric Ramsey Problems

Low-Dimensional Embedding with Extra Information

Similar Documents

Low-Dimensional Embedding with Extra Information

Embedding Tree Metrics into Low-Dimensional Euclidean Spaces

Consistent Digital Rays

Volume in General Metric Spaces

Four-Dimensional Regular Polyhedra

Grid Embedding of 4-Connected Plane Graphs

Three-Dimensional Delaunay Mesh Generation

Linkless and Flat Embeddings in 3-Space

Some Low Distortion Metric Ramsey Problems

Low-Dimensional Embedding with Extra Information