Queries with Segments in Voronoi DiagramsAbstract: 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(nlog^{3}n) 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" } |