Queries with segments in Voronoi diagrams

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 point s P can determine the closest point in P to a query segment outside the con vex 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) tim e. Nearest foreign neighbors or Hausdorff distance for disjoint, colored se gments can be computed in the same time. We explore some connections to Hop croft's problem. (C) 2000 Elsevier Science B.V. All rights reserved.