In this paper we consider proximity problems in which the queries are line segments in the plane. We build a query structure that for a set of n points P can determine the closest point in P to a query segment outside the convex hull of P in O(log n) time. With this we solve the problem of computing the closest point to each of n disjoint line segments in O(n log3 n) time. Nearest foreign neighbors or HausdoriT distance for disjoint, colored segments can be computed in the same time. We explore some connections to Hopcroft's problem.
The problem of locating the nearest point to a query line segment among a set P of n points in the plane was addressed in REF .
Queries with segments in Voronoi diagrams
SODA '99
Computer Science Mathematics