@article {15565,
title = {Proximity problems on line segments spanned by points},
journal = {Computational Geometry},
volume = {33},
year = {2006},
month = {2006/02//},
pages = {115 - 129},
abstract = {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.},
keywords = {Closest, Farthest, k closest lines, Minimum (maximum) area triangle, Proximity problem},
isbn = {0925-7721},
doi = {10.1016/j.comgeo.2005.08.007},
url = {http://www.sciencedirect.com/science/article/pii/S0925772105000805},
author = {Daescu,Ovidiu and Luo,Jun and Mount, Dave}
}