Lower Bounds for the Complexity of the Voronoi Diagram of Polygonal Curves under the Discrete Frechet Distance

2007/08/14 by Kevin Buchin, Buchin, Kevin, Maike Buchin +1
Computer Science · #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #F.2.2 #FOS: Computer and information sciences #Graph Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.0708.1909

openalex publication_date 2007/08/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give lower bounds for the combinatorial complexity of the Voronoi diagram of polygonal curves under the discrete Frechet distance. We show that the Voronoi diagram of n curves in R^d with k vertices each, has complexity Omega(n^dk) for dimension d=1,2 and Omega(n^d(k-1)+2) for d>2.

Related

• Lower bound on the Voronoi diagram of lines in ℝ^d
• Voronoi Diagram of Polygonal Chains under the Discrete Fréchet Distance
• Voronoi diagrams of algebraic varieties under polyhedral norms
• On the Expected Complexity of Voronoi Diagrams on Terrains
• Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework