Queries with Segments in Voronoi Diagrams

Abstract: 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 S can determine the closest point in S to a query segment outside the convex hull of S in O(nlogn) time. With this we solve the problem of computing the closest point to each of n disjoint line segments in O(nlog3n) time. Nearest foreign neighbors or Hausdorff distance for disjoint, colored segments can be computed in the same time. We explore some connections to Hopcroft's problem.

author = "S. Bespamyatnikh and J. Snoeyink",
title = "Queries with Segments in Voronoi Diagrams",
journal = "Comput. Geom. Theory Appl.",
year = 2000,
volume = 16,
number = 1,
pages = "23--33"