- journal article metadata
European Mathematical Society Publishing House
2016-09-19 17:05:23
Portugaliae Mathematica
Port. Math.
PM
0032-5155
1662-2758
General
10.4171/PM
http://www.ems-ph.org/doi/10.4171/PM
subscribers
European Mathematical Society Publishing House
Zuerich, Switzerland
© European Mathematical Society (from 2008)
68
2011
1
Euclidean distance matrices, semidefinite programming and sensor network localization
Abdo
Alfakih
University of Windsor, WINDSOR, ONTARIO, CANADA
Philippe
Charron
Université de Montréal, Montréal, QC, CANADA
Veronica
Piccialli
Università di Roma Tor Vergata, ROMA, ITALY
Henry
Wolkowicz
University of Waterloo, WATERLOO, ONTARIO, CANADA
Euclidean distance matrix completions, sensor network localization, fundamental problem of distance geometry, semidefinite programming
The fundamental problem of distance geometry involves the characterization and study of sets of points based only on given values of some or all of the distances between pairs of points. This problem has a wide range of applications in various areas of mathematics, physics, chemistry, and engineering. Euclidean distance matrices play an important role in this context by providing elegant and powerful convex relaxations. They play an important role in problems such as graph realization and graph rigidity. Moreover, by relaxing the embedding dimension restriction, these matrices can be used to approximate the hard problems efficiently using semidefinite programming. Throughout this survey we emphasize the interplay between these concepts and problems. In addition, we illustrate this interplay in the context of the sensor network localization problem.
Geometry
Convex and discrete geometry
Operations research, mathematical programming
General
53
102
10.4171/PM/1881
http://www.ems-ph.org/doi/10.4171/PM/1881