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

Korea Advanced Institute of Science and Technology
LORIA Laboratoire Lorrain de Recherche en Informatique et ses Applications
Commonwealth Scientific and Industrial Research Organization
Soongsil University

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

Résumé

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.

langue originale	Anglais
titre	Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings
Editeur	Springer Verlag
Pages	407-418
Nombre de pages	12
ISBN (imprimé)	9783540755197
Les DOIs	https://doi.org/10.1007/978-3-540-75520-3_37
état	Publié - 1 janv. 2007
Modification externe	Oui
Evénement	15th Annual European Symposium on Algorithms, ESA 2007 - Eilat, Israël Durée: 8 oct. 2007 → 10 oct. 2007

Série de publications

Nom	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4698 LNCS
ISSN (imprimé)	0302-9743
ISSN (Electronique)	1611-3349

Une conférence

Une conférence	15th Annual European Symposium on Algorithms, ESA 2007
Pays/Territoire	Israël
La ville	Eilat
période	8/10/07 → 10/10/07

Accès au document

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

Contient cette citation

Cheong, O., Everett, H., Glisse, M., Gudmundsson, J., Hornus, S., Lazard, S., Lee, M., & Na, H. S. (2007). Farthest-polygon voronoi diagrams. Dans Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings (p. 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. Dans 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, p. 407-418, 15th Annual European Symposium on Algorithms, ESA 2007, Eilat, Israël, 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).

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

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.

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. Dans 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

Résumé

Série de publications

Une conférence

Accès au document

Empreinte digitale

Contient cette citation