pith. sign in

arxiv: 2605.23073 · v1 · pith:G577XMFVnew · submitted 2026-05-21 · 💻 cs.DM

Positional Identifiability from Pairwise Collision Data

Yun-Han Li , Ilan Shomorony , Olgica Milenkovic This is my paper

Pith reviewed 2026-05-25 05:10 UTC · model grok-4.3

classification 💻 cs.DM
keywords positional identifiabilitypairwise collisionscollision graphsinterval graphsgraph connectivitygraph completionNP-hardnessreal line motion
0
0 comments X

The pith

Relative positions of objects on a line are uniquely recoverable from pairwise collision data if and only if the collision graph is connected.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that full observation of both colliding pairs and their order allows unique recovery of relative positions exactly when the graph formed by those collisions is connected. This condition matters because it supplies a simple graphical test for when interaction records alone suffice to reconstruct the arrangement without any direct position or velocity measurements. For observations that lack timing information the recovery problem reduces to decomposing the graph into maximal cliques whose contraction yields an interval graph, admitting efficient algorithms. When some collision observations are missing the task becomes a graph-completion problem shown to be NP-hard through its relation to the bandwidth problem.

Core claim

Under the full observability model, in which both the set of collisions and their temporal ordering are known, the relative positions of all objects can be uniquely recovered if and only if the collision history, represented as a graph, is connected.

What carries the argument

The collision history graph whose edges are the observed pairwise meetings; its connectivity decides whether the mapping from positions to observed collision sequences is injective.

If this is right

  • When the collision graph is connected the ordered collision record determines the relative ordering and spacing of all objects.
  • Without timing information the problem admits a canonical layer decomposition into maximal cliques.
  • The graph obtained by contracting each maximal clique is an interval graph.
  • Recovering the structure under incomplete observations is NP-hard and admits a 4-approximation via the graph bandwidth problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The connectivity criterion could guide the design of controlled experiments that add artificial interactions to guarantee identifiability.
  • The reduction to interval graphs suggests possible algorithmic transfers from other linear-arrangement problems such as interval scheduling.
  • Noise or simultaneous collisions would require a probabilistic extension of the deterministic connectivity condition.

Load-bearing premise

Objects move continuously along the real line so that every collision is a distinct pairwise meeting and no two objects share the same velocity.

What would settle it

Construct two distinct position assignments for the same set of objects whose induced collision sequences are identical whenever the collision graph is disconnected.

Figures

Figures reproduced from arXiv: 2605.23073 by Ilan Shomorony, Olgica Milenkovic, Yun-Han Li.

Figure 1
Figure 1. Figure 1: An example with four curves and six collisions. By sequen [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An example of module shrinking with five curves and nine collisions: v2(t), v4(t), colored red, intersect the remaining three curves in the same way. Therefore, we can “shrink” the two of them together vertically by an ϵ factor until they almost become one thin line (dashed), then paste it following any of the original red curves (in this example, v2(t)). The function graph remains the same after replacing… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript claims three main results on recovering relative positions of objects moving on the real line from pairwise collision data. Under the full observability model (set of collisions and their temporal ordering known), relative positions are uniquely recoverable if and only if the collision history graph is connected. Under partial observability (only colliding pairs observed, without timing), the problem relates to function graphs; a canonical layer decomposition is introduced in which each layer corresponds to a maximal clique, the induced contraction graph is an interval graph, and efficient algorithms recover it. Under incomplete observations (some pairwise collisions missing), the problem is a graph completion task shown to be NP-hard via a 4-approximation relationship to the graph bandwidth problem.

Significance. If the derivations hold, the work supplies foundational identifiability and reconstruction results for interaction-based sensing, cleanly linking the full-observability case to graph connectivity and the partial case to interval graphs with algorithmic consequences. The explicit if-and-only-if characterization and the reduction to a known graph problem are strengths that could guide practical system design.

major comments (2)
  1. [Abstract and hardness section] Abstract (third contribution) and the corresponding hardness section: the NP-hardness claim for the incomplete-observations graph-completion problem is stated as holding 'via a 4-approximation relationship with the graph bandwidth problem.' An approximation factor does not by itself establish NP-hardness; the manuscript must supply the explicit polynomial-time reduction (including direction and how the factor of 4 is used) to support the central claim.
  2. [Full-observability result] Full-observability theorem (likely the first main result section): the if-and-only-if statement for unique positional recovery assumes continuous motion on the line with no degeneracies (distinct velocities, no simultaneous multi-object collisions). These conditions are necessary for the mapping to be injective but are not listed explicitly alongside the theorem, leaving the precise scope of the central claim unclear.
minor comments (2)
  1. [Partial-observability section] Clarify the definition of 'function graphs' and 'canonical layer decomposition' on first use, and ensure the contraction operation is defined before the interval-graph claim.
  2. [Abstract] The abstract's phrasing of the hardness result should be aligned with the precise statement in the body once the reduction is detailed.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments, which help clarify the presentation of our results. We address each major comment below.

read point-by-point responses

  1. Referee: [Abstract and hardness section] Abstract (third contribution) and the corresponding hardness section: the NP-hardness claim for the incomplete-observations graph-completion problem is stated as holding 'via a 4-approximation relationship with the graph bandwidth problem.' An approximation factor does not by itself establish NP-hardness; the manuscript must supply the explicit polynomial-time reduction (including direction and how the factor of 4 is used) to support the central claim.

    Authors: We agree that the current phrasing is imprecise and does not constitute a complete proof of NP-hardness. The manuscript's intent was to indicate that hardness follows from a polynomial-time reduction to the known NP-hard bandwidth problem, with the factor of 4 arising in the approximation-preserving construction. In the revised manuscript we will include the explicit reduction (from bandwidth to our completion problem), specify the direction, and detail how the factor of 4 is used to establish the hardness result. revision: yes

  2. Referee: [Full-observability result] Full-observability theorem (likely the first main result section): the if-and-only-if statement for unique positional recovery assumes continuous motion on the line with no degeneracies (distinct velocities, no simultaneous multi-object collisions). These conditions are necessary for the mapping to be injective but are not listed explicitly alongside the theorem, leaving the precise scope of the central claim unclear.

    Authors: We agree that the modeling assumptions of continuous trajectories, distinct velocities, and absence of simultaneous multi-object collisions are essential to the injectivity claim and should be stated explicitly with the theorem. In the revision we will add a dedicated paragraph immediately preceding the theorem that lists these assumptions and notes that they are required for the if-and-only-if characterization. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's core results are direct mathematical statements: an iff characterization of positional recovery from collision graphs under full observability (connectivity suffices and is necessary), a layer decomposition into maximal cliques whose contraction is an interval graph under partial observability, and an NP-hardness reduction to graph bandwidth under incomplete observations. These are established via standard graph-theoretic arguments and complexity reductions with no fitted parameters, no equations that define a quantity in terms of itself, and no load-bearing self-citations or imported uniqueness theorems. The derivation chain is self-contained against external graph properties and does not reduce any claimed prediction or identifiability result to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard graph-theoretic definitions and assumptions about continuous motion on the line; no free parameters, new entities, or ad-hoc axioms are introduced beyond domain-standard ones.

axioms (1)
  • domain assumption Objects move continuously on the real line with collisions occurring precisely when positions coincide.
    Invoked in the definition of the full and partial observability models to link collision data to positions.

pith-pipeline@v0.9.0 · 5729 in / 1201 out tokens · 23773 ms · 2026-05-25T05:10:15.427246+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    Reality mining: sensing complex social systems,

    N. Eagle and A. Pentland, “Reality mining: sensing complex social systems,” Personal and ubiquitous computing, vol. 10, no. 4, pp. 255–268, 2006

    work page 2006

  2. [2]

    Computational social science,

    D. Lazer, A. Pentland, L. Adamic, S. Aral, A.-L. Barabási, D. Brewer, N. Christakis, N. Contractor, J. Fowler, M. Gutmannet al., “Computational social science,”Science, vol. 323, no. 5915, pp. 721–723, 2009

    work page 2009

  3. [3]

    Intersection graphs of curves in the plane,

    G. Ehrlich, S. Even, and R. E. Tarjan, “Intersection graphs of curves in the plane,”Journal of Combinatorial Theory, Series B, vol. 21, no. 1, pp. 8–20, 1976

    work page 1976

  4. [4]

    E. R. Scheinerman,Intersection classes and multiple intersection parameters of graphs. Princeton University, 1984

    work page 1984

  5. [5]

    Incidence matrices and interval graphs,

    D. Fulkerson and O. Gross, “Incidence matrices and interval graphs,”Pacific journal of mathematics, vol. 15, no. 3, pp. 835–855, 1965

    work page 1965

  6. [6]

    Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms,

    K. S. Booth and G. S. Lueker, “Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms,”Journal of computer and system sciences, vol. 13, no. 3, pp. 335–379, 1976

    work page 1976

  7. [7]

    Transitive orientation of graphs and identification of permutation graphs,

    A. Pnueli, A. Lempel, and S. Even, “Transitive orientation of graphs and identification of permutation graphs,”Canadian Journal of Mathematics, vol. 23, no. 1, pp. 160–175, 1971

    work page 1971

  8. [8]

    Intersection graphs of segments,

    J. Kratochvíl and J. Matousek, “Intersection graphs of segments,”Journal of Combinatorial Theory, Series B, vol. 62, no. 2, pp. 289–315, 1994

    work page 1994

  9. [9]

    M. C. Golumbic,Algorithmic graph theory and perfect graphs. Elsevier, 2004, vol. 57

    work page 2004

  10. [10]

    T. A. McKee and F. R. McMorris,Topics in intersection graph theory. SIAM, 1999

    work page 1999

  11. [11]

    A survey of graph layout problems,

    J. Díaz, J. Petit, and M. Serna, “A survey of graph layout problems,”ACM Computing Surveys (CSUR), vol. 34, no. 3, pp. 313–356, 2002

    work page 2002

  12. [12]

    Addenda to the survey of layout problems,

    J. Petit, “Addenda to the survey of layout problems,”Bulletin of EATCS, vol. 3, no. 105, 2013

    work page 2013

  13. [13]

    Approximating the bandwidth of caterpillars,

    U. Feige and K. Talwar, “Approximating the bandwidth of caterpillars,” Algorithmica, vol. 55, no. 1, pp. 190–204, 2009

    work page 2009

  14. [14]

    On euclidean embeddings and bandwidth min- imization,

    J. Dunagan and S. Vempala, “On euclidean embeddings and bandwidth min- imization,” inInternational Workshop on Randomization and Approximation Techniques in Computer Science. Springer, 2001, pp. 229–240

    work page 2001

  15. [15]

    Comparability graphs and intersection graphs,

    M. C. Golumbic, D. Rotem, and J. Urrutia, “Comparability graphs and intersection graphs,”Discrete Mathematics, vol. 43, no. 1, pp. 37–46, 1983

    work page 1983

  16. [16]

    Transitiv orientierbare graphen,

    T. Gallai, “Transitiv orientierbare graphen,”Acta Mathematica Hungarica, vol. 18, no. 1-2, pp. 25–66, 1967

    work page 1967