The complexity of bisectors and Voronoi diagrams on realistic terrains

B. Aronov, M. Berg, de, S. Thite

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

10 Citaten (Scopus)

Samenvatting

We prove tight bounds on the complexity of bisectors and Voronoi diagrams on so-called realistic terrains, under the geodesic distance. In particular, if n denotes the number of triangles in the terrain, we show the following two results. (i) If the triangles of the terrain have bounded slope and the projection of the set of triangles onto the xy-plane has low density, then the worst-case complexity of a bisector is T(n). (ii) If, in addition, the triangles have similar sizes and the domain of the terrain is a rectangle of bounded aspect ratio, then the worst-case complexity of the Voronoi diagram of m point sites is T(n+mvn)
Originele taal-2Engels
TitelAlgorithms - ESA 2008 (16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008, Proceedings)
RedacteurenD. Halperin, K. Mehlhorn
Plaats van productieBerlin
UitgeverijSpringer
Pagina's100-111
ISBN van geprinte versie978-3-540-87743-1
DOI's
StatusGepubliceerd - 2008

Publicatie series

NaamLecture Notes in Computer Science
Volume5193
ISSN van geprinte versie0302-9743

Vingerafdruk

Duik in de onderzoeksthema's van 'The complexity of bisectors and Voronoi diagrams on realistic terrains'. Samen vormen ze een unieke vingerafdruk.

Citeer dit