An Expected Linear-Time Algorithm for the Farthest-Segment Voronoi Diagram

2014/11/11 by Elena Khramtcova, Khramtcova, Elena, Evanthia Papadopoulou +1
Computer Science · #Algorithms and Data Compression #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1411.2816

openalex publication_date 2014/11/11 · openalex created_date 2017/12/22 · openalex updated_date 2026/07/28

Abstract

We present an expected linear-time algorithm to construct the farthest-segment Voronoi diagram, given the sequence of its faces at infinity. This sequence forms a Davenport-Schinzel sequence of order 3 and it can be computed in O(n log n) time, where n is the number of input segments. The farthest-segment Voronoi diagram is a tree, with disconnected Voronoi regions, of total complexity Theta(n) in the worst case. Disconnected regions pose a major difficulty in deriving linear-time construction algorithms for such tree-like Voronoi diagrams. In this paper we present a new approach towards this direction.

Related

• Deletion in abstract Voronoi diagrams in expected linear time and related problems
• Farthest-point Voronoi diagrams in the presence of rectangular obstacles
• Geodesic farthest-point Voronoi diagram in linear time
• An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons
• An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism