Proximity problems on line segments spanned by points

TitleProximity problems on line segments spanned by points
Publication TypeJournal Articles
Year of Publication2006
AuthorsDaescu O, Luo J, Mount D
JournalComputational Geometry
Pagination115 - 129
Date Published2006/02//
ISBN Number0925-7721
KeywordsClosest, Farthest, k closest lines, Minimum (maximum) area triangle, Proximity problem

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.