When Can a System of Subnetworks Be Registered Uniquely?
Aditya Vikram Singh, Kunal N. Chaudhury
Abstract
Consider a network with N nodes in d dimensions, and M overlapping subsets P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> , ⋯,P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</sub> (subnetworks). Assume that the nodes in a given P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> are observed in a local coordinate system. We wish to register the subnetworks using the knowledge of the observed coordinates. More precisely, we want to compute the positions of the N nodes in a global coordinate system, given P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> , ⋯, P <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</sub> and the corresponding local coordinates. Among other applications, this problem arises in divide-and-conquer algorithms for localization of adhoc sensor networks. The network is said to be uniquely registrable if the global coordinates can be computed uniquely (up to a rigid transform). Clearly, if the network is not uniquely registrable, then any registration algorithm whatsoever is bound to fail. We formulate a necessary and sufficient condition for uniquely registra-bility in arbitrary dimensions. This condition leads to a randomized polynomial-time test for unique registrability in arbitrary dimensions, and a combinatorial linear-time test in two dimensions.
BibTeX
@inproceedings{icassp2019_whencanasystemof,
title = {When Can a System of Subnetworks Be Registered Uniquely?},
author = {Aditya Vikram Singh and Kunal N. Chaudhury},
booktitle = {ICASSP 2019},
year = {2019}
}