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 log~3 n)time. Nearst foreign neighbors or Hausdorff distance for disjoint, colored segments can be computed in the same time. We explore some connections to Hopcroft's problem.
展开▼
