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.


@paper{bs-qsvd-00,
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"
}