Linear Theory for Self-Localization: Convexity, Barycentric Coordinates, and Cayley–Menger Determinants
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 angl...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2015-01-01
|
| Series: | IEEE Access |
| Online Access: | https://ieeexplore.ieee.org/document/7180272/ |
| _version_ | 1818331645758930944 |
|---|---|
| author | Usman A. Khan Soummya Kar Jose M. F. Moura |
| author_facet | Usman A. Khan Soummya Kar Jose M. F. Moura |
| author_sort | Usman A. Khan |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-13T13:23:09Z |
| format | Article |
| id | doaj.art-aec4b5f107994abfb3fd5b2bc69ebb4f |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-13T13:23:09Z |
| publishDate | 2015-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-aec4b5f107994abfb3fd5b2bc69ebb4f2022-12-21T23:44:21ZengIEEEIEEE Access2169-35362015-01-0131326133910.1109/ACCESS.2015.24648127180272Linear Theory for Self-Localization: Convexity, Barycentric Coordinates, and Cayley–Menger DeterminantsUsman A. Khan0Soummya Kar1Jose M. F. Moura2Department of Electrical and Computer Engineering, Tufts University, Medford, MA, USADepartment of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, USADepartment of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, USALocalization, 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.https://ieeexplore.ieee.org/document/7180272/ |
| spellingShingle | Usman A. Khan Soummya Kar Jose M. F. Moura Linear Theory for Self-Localization: Convexity, Barycentric Coordinates, and Cayley–Menger Determinants IEEE Access |
| title | Linear Theory for Self-Localization: Convexity, Barycentric Coordinates, and Cayley–Menger Determinants |
| title_full | Linear Theory for Self-Localization: Convexity, Barycentric Coordinates, and Cayley–Menger Determinants |
| title_fullStr | Linear Theory for Self-Localization: Convexity, Barycentric Coordinates, and Cayley–Menger Determinants |
| title_full_unstemmed | Linear Theory for Self-Localization: Convexity, Barycentric Coordinates, and Cayley–Menger Determinants |
| title_short | Linear Theory for Self-Localization: Convexity, Barycentric Coordinates, and Cayley–Menger Determinants |
| title_sort | linear theory for self localization convexity barycentric coordinates and cayley x2013 menger determinants |
| url | https://ieeexplore.ieee.org/document/7180272/ |
| work_keys_str_mv | AT usmanakhan lineartheoryforselflocalizationconvexitybarycentriccoordinatesandcayleyx2013mengerdeterminants AT soummyakar lineartheoryforselflocalizationconvexitybarycentriccoordinatesandcayleyx2013mengerdeterminants AT josemfmoura lineartheoryforselflocalizationconvexitybarycentriccoordinatesandcayleyx2013mengerdeterminants |