Proximity problems on line segments spanned by points

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 log n + k ) time and O ( n + k ) space.