# Approximate Nearest-Neighbor Search for Line Segments

arXiv: https://arxiv.org/abs/2103.16071 · HTML: https://mlsanity.com/paper/2103.16071/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Mar 2021.

## Built on by (most cited first, 1 of 1)

- [Neural Approximation of Generalized Voronoi Diagrams](https://mlsanity.com/paper/2603.26964/) (2026)

## Abstract (arXiv)

Approximate nearest-neighbor search is a fundamental algorithmic problem that continues to inspire study due its essential role in numerous contexts. In contrast to most prior work, which has focused on point sets, we consider nearest-neighbor queries against a set of line segments in ℝd, for constant dimension d. Given a set S of n disjoint line segments in ℝd and an error parameter varepsilon > 0, the objective is to build a data structure such that for any query point q, it is possible to return a line segment whose Euclidean distance from q is at most (1+varepsilon) times the distance from q to its nearest line segment. We present a data structure for this problem with storage O((n2/varepsilond) log (Delta/varepsilon)) and query time O(log (max(n,Delta)/varepsilon)), where Delta is the spread of the set of segments S. Our approach is based on a covering of space by anisotropic elements, which align themselves according to the orientations of nearby segments.