Proximity Problems on Line Segments Spanned by Points.
Ovidiu Daescu, Jun Luo, David M. Mount · Canadian Conference on Computational Geometry · 2005
Finding the closest or farthest line segment (line) from a point are fundamental proximity problems. Given a set S of n points in the plane and another point q, we present optimal O(n log n) time, O(n) space algorithms for finding the closest and farthest line segments (lines) from q among those spanned by the points in S. We further show how to apply our techniques to find the minimum (maximum) area triangle with a vertex at q and the other two vertices in S\{q} in optimal O(n log n) time and O(n) space. Finally, we give an O(n log n) time, O(n) space algorithm to find the kth closest line from q and show how to find the k closest lines from q in O(n logn + k) time and O(n + k) space.