Hazel Everett

  1. Farthest-Polygon Voronoi Diagrams.

    Authors: Joachim Gudmundsson, Otfried Cheong, Hazel Everett, Marc Glisse, Samuel Hornus, Sylvain Lazard, Mira Lee, Hyeon-Suk Na
    Subjects: Computational Geometry
    Abstract

    Given a family of k disjoint connected polygonal sites in general position
    and of total complexity n, we consider the farthest-site Voronoi diagram of
    these sites, where the distance to a site is the distance to a closest point on
    it. We show that the complexity of this diagram is O(n), and give an O(n log^3
    n) time algorithm to compute it. We also prove a number of structural
    properties of this diagram. In particular, a Voronoi region may consist of k-1
    connected components, but if one component is bounded, then it is equal to the
    entire region.

Syndicate content