A remark on global positioning from local distances

Amit Singer

doi:10.1073/pnas.0709842104

A remark on global positioning from local distances

Amit Singer

Research output: Contribution to journal › Article › peer-review

76 Scopus citations

Abstract

Finding the global positioning of points in Euclidean space from a local or partial set of pairwise distances is a problem in geometry that emerges naturally in sensor networks and NMR spectroscopy of proteins. We observe that the eigenvectors of a certain sparse matrix exactly match the sought coordinates. This translates to a simple and efficient algorithm that is robust to noisy distance data.

Original language	English (US)
Pages (from-to)	9507-9511
Number of pages	5
Journal	Proceedings of the National Academy of Sciences of the United States of America
Volume	105
Issue number	28
DOIs	https://doi.org/10.1073/pnas.0709842104
State	Published - Jul 15 2008
Externally published	Yes

All Science Journal Classification (ASJC) codes

General

Keywords

Distance geometry
Eigenvectors
Multidimensional scaling
Sensor networks

Access to Document

10.1073/pnas.0709842104

Cite this

@article{97a2833923d74027bedaeee3dff3f497,

title = "A remark on global positioning from local distances",

abstract = "Finding the global positioning of points in Euclidean space from a local or partial set of pairwise distances is a problem in geometry that emerges naturally in sensor networks and NMR spectroscopy of proteins. We observe that the eigenvectors of a certain sparse matrix exactly match the sought coordinates. This translates to a simple and efficient algorithm that is robust to noisy distance data.",

keywords = "Distance geometry, Eigenvectors, Multidimensional scaling, Sensor networks",

author = "Amit Singer",

year = "2008",

month = jul,

day = "15",

doi = "10.1073/pnas.0709842104",

language = "English (US)",

volume = "105",

pages = "9507--9511",

journal = "Proceedings of the National Academy of Sciences of the United States of America",

issn = "0027-8424",

publisher = "National Academy of Sciences",

number = "28",

}

TY - JOUR

T1 - A remark on global positioning from local distances

AU - Singer, Amit

PY - 2008/7/15

Y1 - 2008/7/15

N2 - Finding the global positioning of points in Euclidean space from a local or partial set of pairwise distances is a problem in geometry that emerges naturally in sensor networks and NMR spectroscopy of proteins. We observe that the eigenvectors of a certain sparse matrix exactly match the sought coordinates. This translates to a simple and efficient algorithm that is robust to noisy distance data.

AB - Finding the global positioning of points in Euclidean space from a local or partial set of pairwise distances is a problem in geometry that emerges naturally in sensor networks and NMR spectroscopy of proteins. We observe that the eigenvectors of a certain sparse matrix exactly match the sought coordinates. This translates to a simple and efficient algorithm that is robust to noisy distance data.

KW - Distance geometry

KW - Eigenvectors

KW - Multidimensional scaling

KW - Sensor networks

UR - http://www.scopus.com/inward/record.url?scp=47749090558&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=47749090558&partnerID=8YFLogxK

U2 - 10.1073/pnas.0709842104

DO - 10.1073/pnas.0709842104

M3 - Article

C2 - 18621694

AN - SCOPUS:47749090558

SN - 0027-8424

VL - 105

SP - 9507

EP - 9511

JO - Proceedings of the National Academy of Sciences of the United States of America

JF - Proceedings of the National Academy of Sciences of the United States of America

IS - 28

ER -

A remark on global positioning from local distances

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this