Positional Identifiability from Pairwise Collision Data

Yun-Han Li, Ilan Shomorony, Olgica MilenkovicarXiv 2026 · arXiv

TL;DR

Can you reconstruct the relative positions of moving objects just by knowing when they bump into each other? This paper maps out the theoretical limits of this problem across three levels of data availability, showing that while perfectly ordered collision histories allow full position reconstruction, missing or unordered data leads to fundamental ambiguities and NP-hard graph completion challenges.

What Problem Does This Paper Address?

In many distributed sensing scenarios—such as tracking particle interactions in physics or monitoring proximity networks in social dynamics—global coordinate data (like GPS or exact trajectories) is unavailable due to limited resolution or privacy constraints. Instead, observers only have access to "local events," specifically when two objects cross paths or collide.

The authors tackle a fundamental question: To what extent can we reconstruct the relative positions of objects moving along a one-dimensional line using only pairwise collision data?

By treating trajectories as continuous functions over time and collisions as intersections, the paper bridges physical motion tracking with the mathematical theory of intersection graphs (such as function graphs and interval graphs).

Methods

The authors analyze the problem by breaking it down into three distinct tiers of observability:

  1. Full Observability (Known Collision Times & Order): The data consists of a complete, chronologically ordered sequence of collisions. The authors use an inductive proof and a novel "trajectory swapping" technique to show how to reconstruct the exact order of objects over time.
  2. Partial Observability (No Timing Information): The data only tells us which pairs of objects collided at least once, but not when or in what order. The authors leverage modular decomposition to simplify the graph and introduce a canonical layer decomposition that groups indistinguishable objects into maximal cliques. They provide two polynomial-time algorithms (Algorithms 1 and 2) to recover these layers.
  3. Incomplete Observations (Missing Collisions): Some collision edges are entirely missing from the observed graph. The authors frame this as a graph completion problem aimed at minimizing the maximum degree of the completed graph (which corresponds to minimizing the worst-case constraints on the trajectories).

Datasets

Not discussed in the paper. As a purely theoretical and combinatorial study, the paper relies on rigorous mathematical proofs and algorithmic analysis rather than empirical datasets or training benchmarks.

Key Insights and Ideas

  • Connectivity Equals Identifiability: In the full observability case, you don't need global coordinates to know where everyone is. As long as the collision multigraph is connected, the relative order of all objects at all times can be uniquely determined (up to a total spatial reversal).
  • The Trajectory Swapping Trick: To prove full identifiability, the authors introduce a conceptual tool where the future paths of colliding objects are swapped so they "touch but don't cross." This straightens out any complex collision history into a simple path graph where positions are trivial to read, allowing the original positions to be unpacked in reverse order.
Trajectory swapping trick to simplify collision histories
  • The Ambiguity of Cliques: Without timing data, objects that form a maximal clique (where every object in the group collides with every other object) cannot be ordered relative to one another. However, the macro-relationship between these cliques forms a clean, linear interval graph structure that can be efficiently recovered.
Module shrinking in function graphs

Key Results

  • Full Observability: Unique position recovery is proven to be possible if and only if the collision history graph is connected.
  • Partial Observability: The authors successfully design a polynomial-time framework to perfectly extract the canonical layer decomposition and its corresponding interval contraction graph, defining the exact limits of what can be known without timestamps.
  • Incomplete Observations: The authors prove that finding the optimal function graph completion to minimize the maximum degree is NP-hard. However, they establish that this problem is a 4-approximation of the classic graph bandwidth problem, connecting their work to deeply studied graph layout challenges.

Limitations and Future Work

  • Module Assumptions: The partial observability algorithms assume that the graph contains no non-trivial modules, relying on standard preprocessing techniques to handle them.
  • Interleaving with Folding: A major open problem highlighted by the authors occurs when two independent collision graphs share a single vertex and both have missing edges. Finding an efficient algorithm to interleave their layer sequences to minimize bandwidth (a process they term "interleaving with folding") remains unresolved.
  • Dimensionality Constraints: The physical model is strictly limited to one-dimensional motion along a line. Extending this framework to 2D or 3D trajectories introduces significantly more complex topological intersection challenges (e.g., string graphs), which remain open for future exploration.

Summary updated

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 \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.
BibTeX
@misc{li2026positional,
  author = {Yun-Han Li and Ilan Shomorony and Olgica Milenkovic},
  title = {{Positional Identifiability from Pairwise Collision Data}},
  year = {2026},
  eprint = {2605.23073},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.23073},
}
Figure