Algorithms for Computing Closest Points for Segments

2024/01/05 by Wang, Haitao
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2401.02636

Abstract

Given a set P of n points and a set S of n segments in the plane, we consider the problem of computing for each segment of S its closest point in P. The previously best algorithm solves the problem in n^4/32^{O(log^*n)} time [Bespamyatnikh, 2003] and a lower bound (under a somewhat restricted model) Ω(n^4/3) has also been proved. In this paper, we present an O(n^4/3) time algorithm and thus solve the problem optimally (under the restricted model). In addition, we also present data structures for solving the online version of the problem, i.e., given a query segment (or a line as a special case), find its closest point in P. Our new results improve the previous work.

Related

• Approximate Nearest-Neighbor Search for Line Segments
• Searching for the closest-pair in a query translate
• Efficient Nearest-Neighbor Query and Clustering of Planar Curves
• Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
• Closest-Pair Queries in Fat Rectangles