Proximity problems on line segments spanned by points (Q2489537)

Given a set \(S\) of \(n\) points and another point \(q\), the authors study the problem of finding the closest or farthest line segment (line) from \(q\) among those spanned by points in \(S\). They present an algorithm with \(O(n\log n)\) time and \(O(n)\) space for computing an optimal solution.