The complexity of bisectors and Voronoi diagrams on realistic terrains

Boris Aronov; Mark De Berg; Shripad Thite

doi:10.1007/978-3-540-87744-8_9

The complexity of bisectors and Voronoi diagrams on realistic terrains

Boris Aronov, Mark De Berg, Shripad Thite

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 Θ(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).

Original language	English (US)
Title of host publication	Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings
Publisher	Springer Verlag
Pages	100-111
Number of pages	12
ISBN (Print)	3540877436, 9783540877431
DOIs	https://doi.org/10.1007/978-3-540-87744-8_9
State	Published - 2008
Event	16th Annual European Symposium on Algorithms, ESA 2008 - Karlsruhe, Germany Duration: Sep 15 2008 → Sep 17 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5193 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	16th Annual European Symposium on Algorithms, ESA 2008
Country/Territory	Germany
City	Karlsruhe
Period	9/15/08 → 9/17/08

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Aronov, B., De Berg, M., & Thite, S. (2008). The complexity of bisectors and Voronoi diagrams on realistic terrains. In Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings (pp. 100-111). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5193 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-87744-8_9

The complexity of bisectors and Voronoi diagrams on realistic terrains. / Aronov, Boris; De Berg, Mark; Thite, Shripad.
Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings. Springer Verlag, 2008. p. 100-111 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5193 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Aronov, B, De Berg, M & Thite, S 2008, The complexity of bisectors and Voronoi diagrams on realistic terrains. in Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5193 LNCS, Springer Verlag, pp. 100-111, 16th Annual European Symposium on Algorithms, ESA 2008, Karlsruhe, Germany, 9/15/08. https://doi.org/10.1007/978-3-540-87744-8_9

Aronov B, De Berg M, Thite S. The complexity of bisectors and Voronoi diagrams on realistic terrains. In Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings. Springer Verlag. 2008. p. 100-111. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-87744-8_9

@inproceedings{f254c78285444ef7811830b7055d4ff9,

title = "The complexity of bisectors and Voronoi diagrams on realistic terrains",

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 Θ(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).",

author = "Boris Aronov and {De Berg}, Mark and Shripad Thite",

year = "2008",

doi = "10.1007/978-3-540-87744-8_9",

language = "English (US)",

isbn = "3540877436",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "100--111",

booktitle = "Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings",

note = "16th Annual European Symposium on Algorithms, ESA 2008 ; Conference date: 15-09-2008 Through 17-09-2008",

}

TY - GEN

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

AU - Aronov, Boris

AU - De Berg, Mark

AU - Thite, Shripad

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 -

The complexity of bisectors and Voronoi diagrams on realistic terrains

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this