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

2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/136064We 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.6 pages, 2 figuresComputational GeometryComputational ComplexityF.2.2Lower Bounds for the Complexity of the Voronoi Diagram of Polygonal Curves under the Discrete Frechet Distancetext