Positional Identifiability from Pairwise Collision Data
Yun-Han Li, Ilan Shomorony and Olgica Milenkovic · 2026
Read Positional Identifiability from Pairwise Collision Data by Yun-Han Li, Ilan Shomorony and Olgica Milenkovic (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-23073.txt.
Introduction
Li, Shomorony, and Milenkovic study recovering positions of objects moving on a line from pairwise collision data alone. With full observability, where collision sets and time order are known, positions are recoverable exactly when the collision graph is connected. With partial observability and no timing, the problem connects to function graphs. A standard layer decomposition yields an interval graph with fast methods. With incomplete data and missing collisions, the problem becomes graph completion, shown NP-hard via bandwidth.
Catalog record
| CREATOR | Yun-Han Li, Ilan Shomorony and Olgica Milenkovic |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35215 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.23073
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Positional Identifiability from Pairwise Collision Data Yun-Han Li, Ilan Shomorony and Olgica Milenkovic Abstract 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 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 4 -approximation relationship with the graph bandwidth problem. I Introduction In many practical distributed sensing systems, global knowledge must be inferred based on observed local interactions [ 1 , 2 ] . Most often, the full history of the system evolution is not available, and one only has access to information pertaining to “local events” such as object collisions or interactions. A natural question in this setting is whether such local interaction information allows one to recover an underlying position of objects or the geometry of object movements and encounters. Here, we consider a combinatorial model in which a collection of objects move along the real line (or an interval) according to unknown continuous trajectories. Instead of observing the exact positions of the objects, we only observe pairwise collisions on the line, with or without timestamps for the events. The question of interest is to determine to what extent can one reconstruct the relative positions of objects from such collision information. Interaction-based observations arise naturally in a variety of settings, including particle physics or sensing systems with limited resolution [ 1 ] . In these scenarios, precise positional information of the objects is not directly observable, and one only has access to information about which pairs of objects interacted. As a result, the position of the objects must be inferred indirectly. The goal of this paper is to demonstrate that the problem can be cast in a combinatorial framework in which objects are represented by continuous functions, and observations correspond to pairwise intersections of the functions. The resulting formulation is closely related to function graphs , a class of intersection graphs in which vertices correspond to one-dimensional continuous functions and edges indicate the existence of an intersection [ 3 , 4 ] . More broadly, this places our problem within the extensive literature on intersection graphs, including interval graphs [ 5 , 6 ] , circular-arc graphs, permutation graphs [ 7 ] , and string graphs [ 8 , 9 , 10 ] . While these graph classes have been extensively studied from the perspectives of recognition and structural characterization [ 9 , 10 ] , the question of what positional information can be recovered from intersection data is new. In particular, we investigate how different levels of observability, such as temporal information or the presence of missing interactions, affect our ability to recover the relative positions of objects. Formally, we consider n objects V=\{v_{1},v_{2},\ldots,v_{n}\} whose positions evolve according to unknown continuous trajectories v_{i}(t):\mathbb{R}\to\mathbb{R} . A collision between objects i and j occurs at time t if v_{i}(t)=v_{j}(t) . We study three levels of observability and the resulting types of collision data: 1. Full observability (collision times are known): The observation is the complete ordered (wrt time) sequence of collisions h=e_{1},e_{2},\ldots , equivalently represented as an edge-labeled multigraph H=(V,E) where edge labels encode temporal order. We show that the relative positions p_{k} of all objects at all time can be uniquely recovered (up to reversal) if and only if H is connected. 2. Partial observability (no timing information): The collisions are described by a graph G=(V,E) , where uv\in E indicates that u and v had collided at some time, without ordering information. This model is closely related to function graphs [ 3 , 9 , 10 ] , a well-studied class of intersection graphs. Exact recovery of positions is generally impossible in this setting. Instead, we introduce a canonical layer decomposition (V_{1},V_{2},\ldots,V_{k}) – a partition of V where each layer V_{i} is a maximal clique of objects whose relative order cannot be distinguished from unordered collisions alone. We show that the contraction graph induced by this decomposition is an interval graph [ 5 , 6 ] and provide efficient algorithms to recover it. 3. Incomplete observations (missing collisions): The observation is a subgraph G=(V,E) of the true collision graph, where some collision edges may be absent. We study the problem of completing G into a valid function graph G^{\prime}=(V,E^{\prime}) with E\subseteq E^{\prime} while preserving as much positional information as possible. We show that a natural formulation of this completion problem is a 4 -approximation for the graph bandwidth problem [ 11 , 12 ] , implying NP-hardness [ 13 ] and connecting our setting to classical graph layout problems [ 11 , 12 , 14 , 13 ] . Our work takes a step towards a systematic understanding of positional identifiability from pairwise interaction data, bridging ideas from intersection graph [ 3 , 9 , 10 ] and graph layout problems [ 11 , 12 ] . II Problem Formulation We start by introducing our model movement constraints and observation assumptions. Movement model. There are n objects, V=\{v_{1},v_{2},\ldots,v_{n}\}, whose positions change in time following trajectories described by continuous functions v_{i}(t):\mathbb{R}\rightarrow\mathbb{R} . The trajectories are not known a priori . Observation model. We say that a collision e=v_{i}v_{j} of two objects i and j , or correspondingly, their trajectories v_{i},v_{j} , occurs at time t if v_{i}(t)=v_{j}(t) (i.e., the trajectories intersect). For simplicity, we assume that (1) collisions are instantaneous so that the trajectories intersect only at one time point t instead on overlapping on a time interval [t^{-},t^{+}] ; This is possible since we do not put any constraints on hidden trajectories except continuity. (2) there is at most one collision among trajectories for any t , which also implies that no three or more trajectories intersecting at the same time point; (3) v_{i}(t) and v_{j}(t) always cross when a collision happens (i.e., v_{i}(t^{-})<v_{j}(t^{-})\Rightarrow v_{i}(t^{+})>v_{j}(t^{+}) ). The history of collisions is a sequence of ordered collision times h=e_{1},e_{2},\ldots , where e_{i} is the i -th collision. Equivalently, the collision history can be characterized by the edge-labeled collision multigraph H=(V,E=\{e_{i}\}) , where the edge labels indicate the collision observation orders. Example II.1 The collision graph corresponding to the functions in Figure 2 (left) is G=(V,E) with V=\{v_{i}\}_{i=1}^{4} and E=\{e_{1}=v_{3}v_{4},e_{2}=v_{2}v_{3},e_{3}=v_{1}v_{4},e_{4}=v_{1}v_{4},e_{5}=v_{2}v_{4},e_{6}=v_{3}v_{4}\} . Goal. We say that p_{k}=\left(v_{i_{1}},v_{i_{2}},v_{i_{3}},\ldots\right) are the positions of vertices V=\{v_{1},v_{2},\ldots,v_{n}\} between consecutive collisions e_{k} and e_{k+1} if v_{i_{1}}(t)<v_{i_{2}}(t)<v_{i_{3}}(t)<\ldots for all t between the