The complexity of bisectors and Voronoi diagrams on realistic terrains

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

10 Citations (Scopus)

Abstract

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)
Original languageEnglish
Title of host publicationAlgorithms - ESA 2008 (16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008, Proceedings)
EditorsD. Halperin, K. Mehlhorn
Place of PublicationBerlin
PublisherSpringer
Pages100-111
ISBN (Print)978-3-540-87743-1
DOIs
Publication statusPublished - 2008

Publication series

NameLecture Notes in Computer Science
Volume5193
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'The complexity of bisectors and Voronoi diagrams on realistic terrains'. Together they form a unique fingerprint.

Cite this