Positional Identifiability from Pairwise Collision Data
For researchers in sensor networks or robotics using collision-based sensing, this paper provides a theoretical foundation for positional recovery from collision data, though results are largely theoretical and incremental.
This paper studies the problem of recovering relative positions of objects on a line from pairwise collision data. It provides necessary and sufficient conditions for identifiability under full observability, relates partial observability to function graphs and interval graphs, and shows NP-hardness under incomplete observations via a 4-approximation to graph bandwidth.
We study the problem of recovering the relative positions of objects moving along the real line based only on pairwise collision data. While interaction-based sensing systems arise naturally in a variety of practical settings, a systematic theoretical understanding of positional identifiability from collision observations alone remains unexplored. Our contributions are three-fold. First, under the full observability model, in which both the set of collisions and their temporal ordering are known, we show that the relative positions of all objects can be uniquely recovered if and only if the collision history, represented as a graph, is connected. Second, we show that under partial observability, where only colliding pairs are observed without timing information, the problem is related to \emph{function graphs} and introduce a canonical layer decomposition in which each layer corresponds to a maximal clique; the contraction graph induced by this decomposition is an interval graph, and we provide efficient algorithms to recover it. Third, under incomplete observations where even some pairwise collision observations may be missing, we formulate the problem as a graph completion problem and establish its NP-hardness via a $4$-approximation relationship with the graph bandwidth problem.