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

Simple item page
dc.creatorBuchin, Kevin
dc.creatorBuchin, Maike
dc.date2007-08-14
dc.date.accessioned2026-07-07T08:23:37Z
dc.date.available2026-07-07T08:23:37Z
dc.descriptionWe 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.
dc.description6 pages, 2 figures
dc.identifierhttps://arxiv.org/abs/0708.1909
dc.identifierhttp://arxiv.org/abs/0708.1909
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/136064
dc.subjectComputational Geometry
dc.subjectComputational Complexity
dc.subjectF.2.2
dc.titleLower Bounds for the Complexity of the Voronoi Diagram of Polygonal Curves under the Discrete Frechet Distance
dc.typetext

Files

Collections

arXiv