Farthest-polygon voronoi diagrams

Otfried Cheong; Hazel Everett; Marc Glisse; Joachim Gudmundsson; Samuel Hornus; Sylvain Lazard; Mira Lee; Hyeon Suk Na

doi:10.1007/978-3-540-75520-3_37

Farthest-polygon voronoi diagrams

Otfried Cheong
, Hazel Everett
, Marc Glisse
, Joachim Gudmundsson
, Samuel Hornus
, Sylvain Lazard
, Mira Lee
, Hyeon Suk Na

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

Abstract

Given a family of k disjoint connected polygonal sites of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest point on it. We show that the complexity of this diagram is O(n), and give an O(n log³ n) time algorithm to compute it.

Original language	English
Title of host publication	Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings
Publisher	Springer Verlag
Pages	407-418
Number of pages	12
ISBN (Print)	9783540755197
DOIs	https://doi.org/10.1007/978-3-540-75520-3_37
Publication status	Published - 1 Jan 2007
Externally published	Yes
Event	15th Annual European Symposium on Algorithms, ESA 2007 - Eilat, Israel Duration: 8 Oct 2007 → 10 Oct 2007

Publication series

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

Conference

Conference	15th Annual European Symposium on Algorithms, ESA 2007
Country/Territory	Israel
City	Eilat
Period	8/10/07 → 10/10/07

Access to Document

10.1007/978-3-540-75520-3_37

Cite this

Cheong, O., Everett, H., Glisse, M., Gudmundsson, J., Hornus, S., Lazard, S., Lee, M., & Na, H. S. (2007). Farthest-polygon voronoi diagrams. In Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings (pp. 407-418). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4698 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-75520-3_37

@inproceedings{d24f580db8c3433db2b4a6bcf4d6b1fe,

title = "Farthest-polygon voronoi diagrams",

abstract = "Given a family of k disjoint connected polygonal sites of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest point on it. We show that the complexity of this diagram is O(n), and give an O(n log3 n) time algorithm to compute it.",

author = "Otfried Cheong and Hazel Everett and Marc Glisse and Joachim Gudmundsson and Samuel Hornus and Sylvain Lazard and Mira Lee and Na, \{Hyeon Suk\}",

year = "2007",

month = jan,

day = "1",

doi = "10.1007/978-3-540-75520-3\_37",

language = "English",

isbn = "9783540755197",

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

publisher = "Springer Verlag",

pages = "407--418",

booktitle = "Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings",

note = "15th Annual European Symposium on Algorithms, ESA 2007 ; Conference date: 08-10-2007 Through 10-10-2007",

}

Cheong, O, Everett, H, Glisse, M, Gudmundsson, J, Hornus, S, Lazard, S, Lee, M & Na, HS 2007, Farthest-polygon voronoi diagrams. in Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4698 LNCS, Springer Verlag, pp. 407-418, 15th Annual European Symposium on Algorithms, ESA 2007, Eilat, Israel, 8/10/07. https://doi.org/10.1007/978-3-540-75520-3_37

Farthest-polygon voronoi diagrams. / Cheong, Otfried; Everett, Hazel; Glisse, Marc et al.
Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings. Springer Verlag, 2007. p. 407-418 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4698 LNCS).

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

TY - GEN

T1 - Farthest-polygon voronoi diagrams

AU - Cheong, Otfried

AU - Everett, Hazel

AU - Glisse, Marc

AU - Gudmundsson, Joachim

AU - Hornus, Samuel

AU - Lazard, Sylvain

AU - Lee, Mira

AU - Na, Hyeon Suk

PY - 2007/1/1

Y1 - 2007/1/1

N2 - Given a family of k disjoint connected polygonal sites of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest point on it. We show that the complexity of this diagram is O(n), and give an O(n log3 n) time algorithm to compute it.

AB - Given a family of k disjoint connected polygonal sites of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest point on it. We show that the complexity of this diagram is O(n), and give an O(n log3 n) time algorithm to compute it.

UR - https://www.scopus.com/pages/publications/38049027918

U2 - 10.1007/978-3-540-75520-3_37

DO - 10.1007/978-3-540-75520-3_37

M3 - Conference contribution

AN - SCOPUS:38049027918

SN - 9783540755197

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

SP - 407

EP - 418

BT - Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings

PB - Springer Verlag

T2 - 15th Annual European Symposium on Algorithms, ESA 2007

Y2 - 8 October 2007 through 10 October 2007

ER -

Cheong O, Everett H, Glisse M, Gudmundsson J, Hornus S, Lazard S et al. Farthest-polygon voronoi diagrams. In Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings. Springer Verlag. 2007. p. 407-418. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-75520-3_37

Farthest-polygon voronoi diagrams

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this