Linear Theory for Self-Localization: Convexity, Barycentric Coordinates, and Cayley-Menger Determinants

Usman A. Khan, Soummya Kar, José M. F. MouraIEEE Access 2015 · OpenReview

Introduction

Localization—the process of determining an object's position relative to known "anchors"—is a cornerstone of modern robotics and the Internet of Things (IoT). Traditionally, this task is framed as a nonlinear optimization problem. For instance, using distances leads to trilateration (solving circle equations), while using angles leads to triangulation (applying the law of sines). In large-scale IoT deployments, centralized nonlinear solvers are often computationally prohibitive and scale poorly. Distributed alternatives frequently struggle with local minima or require complex, iterative optimization.

This paper reviews DILOC (Distributed Localization), an algorithm that fundamentally shifts the paradigm by transforming self-localization into a linear iterative process. By leveraging barycentric coordinates and Cayley-Menger determinants, DILOC allows sensors to determine their exact coordinates using only local communication and distance measurements, provided they are situated within the convex hull of anchor nodes.

Geometric Foundations: Barycentric Coordinates and Cayley-Menger Determinants

The core innovation of DILOC is the move away from standard Cartesian $(x, y)$ coordinates in favor of Barycentric Coordinates. In an $m$-dimensional space, any point within a simplex (e.g., a triangle in 2D or a tetrahedron in 3D) can be uniquely represented as a weighted average of the simplex's vertices. These weights, or barycentric coordinates, provide a linear relationship between the point and its neighbors.

To calculate these weights without knowing absolute positions, the algorithm employs Cayley-Menger Determinants. This geometric tool allows a sensor to compute the "hypervolume" (area or volume) of the shapes formed by itself and its neighbors using only pairwise distances.

Sensor 'c' and its neighbors 1, 2, and 3 forming a local convex hull for triangulation.

As shown in the figure above, a sensor 'c' identifies a set of neighbors that enclose it. By measuring the distances between itself and these neighbors, as well as the distances between the neighbors themselves, the sensor can determine its relative position within that local simplex.

Geometric relationships and distances used to calculate barycentric coordinates.

The DILOC Algorithm

The DILOC algorithm operates in a distributed, iterative fashion:

  1. Setup: Each sensor identifies $m+1$ neighbors that form a convex hull around it. It then computes its barycentric coordinates relative to these neighbors using distance measurements and Cayley-Menger determinants.
  2. Iteration: Each sensor begins with an arbitrary initial guess of its position. In each time step, it updates its estimate to be the weighted average of its neighbors' current estimates.
  3. Convergence: The authors model this process as an absorbing Markov chain. Anchors serve as "absorbing states" with fixed positions, while sensors act as "transient states" that eventually converge to their true global coordinates.

Key Insights

  • Linearity through Basis Selection: Localization appears nonlinear primarily due to the use of Cartesian coordinates. Switching to a barycentric basis linearizes the update rule, significantly simplifying the computation.
  • Local to Global Mapping: Even sensors far from anchors can localize correctly as long as there is a path of overlapping convex hulls leading back to the anchors.
  • Geometric Convergence: The update rule functions as a linear contraction map, ensuring that errors decrease geometrically (exponentially), which is ideal for real-time applications.

Results and Performance

The paper demonstrates that under the "structural convexity condition"—where sensors reside within the hull formed by anchors—DILOC is guaranteed to converge to exact coordinates. The algorithm is entirely distributed, requiring each sensor to communicate only with a small set of neighbors.

Simulations on random deployments of up to 500 nodes confirm rapid convergence. Furthermore, the theory generalizes to handle more than $m+1$ neighbors (which can accelerate convergence) and mobile networks. In mobile scenarios, the algorithm can track moving sensors with a bounded tracking error. Extensions like DILAND and DLRE have also been developed to maintain robustness in the presence of measurement noise and packet drops.

Limitations and Future Outlook

While powerful, the linear theory relies on the convexity constraint: sensors must be within the anchor hull. Relaxing this constraint for more arbitrary deployments is an ongoing area of research. Additionally, while any enclosing set of neighbors works, the specific choice of neighbors impacts convergence speed, leaving the problem of "optimal triangulation" open. Finally, maintaining valid triangulation sets in highly dynamic mobile environments remains a practical challenge for future refinement.

Summary updated

Abstract

Localization, finding the coordinates of an object with respect to other objects with known coordinates—hereinafter, referred to as anchors, is a nonlinear problem, as it involves solving circle equations when relating distances to Cartesian coordinates, or, computing Cartesian coordinates from angles using the law of sines. This nonlinear problem has been a focus of significant attention over the past two centuries and the progress follows closely with the advances in instrumentation as well as applied mathematics, geometry, statistics, and signal processing. The Internet-of-Things (IoT), with massive deployment of wireless tagged things, has renewed the interest and activity in finding novel, expert, and accurate indoor self-localization methods, where a particular emphasis is on distributed approaches. This paper is dedicated to reviewing a notable alternative to the nonlinear localization problem, i.e., a linear-convex method, based on Khan et al.’s work. This linear solution utilizes relatively unknown geometric concepts in the context of localization problems, i.e., the barycentric coordinates and the Cayley–Menger determinants. Specifically, in an $m$ -dimensional Euclidean space, a set of $m+1$ anchors, objects with known locations, is sufficient (and necessary) to localize an arbitrary collection of objects with unknown locations—hereinafter, referred to as sensors, with a linear-iterative algorithm. To ease the presentation, we discuss the solution under a structural convexity condition, namely, the sensors lie inside the convex hull of at least $m+1$ anchors. Although rigorous results are included, several remarks and discussion throughout this paper provide the intuition behind the solution and are primarily aimed toward researchers and practitioners interested in learning about this challenging field of research. Additional figures and demos have been added as auxiliary material to support this aim.
BibTeX
@inproceedings{khan2015linear,
  author = {Usman A. Khan and Soummya Kar and José M. F. Moura},
  title = {{Linear Theory for Self-Localization: Convexity, Barycentric Coordinates, and Cayley-Menger Determinants}},
  booktitle = {IEEE Access},
  year = {2015},
  url = {https://openreview.net/forum?id=bTyzWY32hR},
}
Figure