%0 Journal Article %J Computational Geometry %D 2006 %T Proximity problems on line segments spanned by points %A Daescu,Ovidiu %A Luo,Jun %A Mount, Dave %K Closest %K Farthest %K k closest lines %K Minimum (maximum) area triangle %K Proximity problem %X 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. %B Computational Geometry %V 33 %P 115 - 129 %8 2006/02// %@ 0925-7721 %G eng %U http://www.sciencedirect.com/science/article/pii/S0925772105000805 %N 3 %R 10.1016/j.comgeo.2005.08.007