TY - GEN

T1 - The complexity of bisectors and Voronoi diagrams on realistic terrains

AU - Aronov, Boris

AU - De Berg, Mark

AU - Thite, Shripad

N1 - Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2008

Y1 - 2008

N2 - 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 Θ(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 Θ(n +m√n).

AB - 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 Θ(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 Θ(n +m√n).

UR - http://www.scopus.com/inward/record.url?scp=57749176352&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=57749176352&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-87744-8_9

DO - 10.1007/978-3-540-87744-8_9

M3 - Conference contribution

AN - SCOPUS:57749176352

SN - 3540877436

SN - 9783540877431

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 100

EP - 111

BT - Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings

PB - Springer Verlag

T2 - 16th Annual European Symposium on Algorithms, ESA 2008

Y2 - 15 September 2008 through 17 September 2008

ER -