Consistent line clustering using geometric hypergraphs

Many datasets are naturally modeled as graphs, where vertices denote entities and edges encode pairwise interactions. However, some problems exhibit higher-order structure that lies beyond this framework. Among the simplest examples is line clustering, in which points in a Euclidean space are grouped into clusters well approximated by line segments. As any two points trivially determine a line, the relevant structure emerges only when considering higher-order tuples. To capture this, we construct a 3-uniform hypergraph by treating sets of three points as hyperedges whenever they are approximately collinear. This geometric hypergraph encodes information about the underlying line segments, which can be extracted using community recovery algorithms. We characterize the fundamental limits of line clustering and establish the near-optimality of hypergraph-based methods. In particular, we derive information-theoretic thresholds for exact and almost exact recovery for noisy observations from intersecting lines in the plane. Finally, we introduce a polynomial-time spectral algorithm that succeeds up to polylogarithmic factors of the information-theoretic bounds.