Portugaliae Mathematica

Full-Text PDF (595 KB) | Table of Contents | PM summary
Volume 68, Issue 1, 2011, pp. 53–102
DOI: 10.4171/PM/1881

Euclidean distance matrices, semidefinite programming and sensor network localization

Abdo Y. Alfakih[1], Philippe Charron[2], Veronica Piccialli[3] and Henry Wolkowicz[4]

(1) Department of Mathematics, University of Windsor, 401 Sunset Ave, N9P 3B4, WINDSOR, ONTARIO, CANADA
(2) Department de Mathématique, Université de Montréal, 2920, Chemin de la Tour, H3T 1J4, Montréal, QC, CANADA
(3) Dipartimento di Ingegneria dell'Impresa, Università di Roma Tor Vergata, Via del Politecnico, 1, 00133, ROMA, ITALY
(4) Combinatorics and Optimization, University of Waterloo, 200 University Avenue West, N2L 3G1, WATERLOO, ONTARIO, CANADA

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.

Keywords: Euclidean distance matrix completions, sensor network localization, fundamental problem of distance geometry, semidefinite programming

Alfakih Abdo, Charron Philippe, Piccialli Veronica, Wolkowicz Henry: Euclidean distance matrices, semidefinite programming and sensor network localization. Port. Math. 68 (2011), 53-102. doi: 10.4171/PM/1881