| HAL-Inria | Publications, software ... of Inria's scientists |
Farthest-Polygon Voronoi Diagrams
Otfried Cheong
1
Hazel Everett
2
Marc Glisse
2
Joachim Gudmundsson
3
Samuel Hornus
1
Sylvain Lazard
2
Mira Lee
1
Hyeon-Suk Na
3
2
VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Otfried Cheong 1
Author
Hazel Everett 2
Mail :
Author Employer institution : Université Nancy 2
Marc Glisse 2
Mail :
Author Employer institution : Université Nancy 2 IdHAL : glisse
Joachim Gudmundsson 3
Author Employer institution : Soongsil University
Samuel Hornus 1
Mail :
Author Employer institution : KAIST IdHAL : samuel-hornus ORCID : https://orcid.org/0000-0002-5051-1250
Sylvain Lazard 2
Mail : Site :
Author IdHAL : sylvain-lazard
Hyeon-Suk Na 3
Author Employer institution : Soongsil University, Seoul
1
KAIST - Department of Electrical Engineering [Korea Advanced Institute of Science and Technology] (335 Gwahak-ro (373-1 Guseong-dong) Yuseong-gu, Daejeon 305-701 Republic of Korea - South Korea)
- KAIST - Korea Advanced Institute of Science and Technology (291 Daehak-ro, Yuseong-gu, Daejeon 34141, Republic of Korea - South Korea)
2
VEGAS - Effective Geometric Algorithms for Surfaces and Visibility (France)
- INRIA Lorraine (615 rue du Jardin Botanique 54600 Villers-lès-Nancy - France)
- Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France)
- LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications (Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex - France)
- Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France)
- UHP - Université Henri Poincaré - Nancy 1 (24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France - France)
- Université Nancy 2 (91 avenue de la Libération, BP 454, 54001 Nancy cedex - France)
- INPL - Institut National Polytechnique de Lorraine (France)
- CNRS - Centre National de la Recherche Scientifique : UMR7503 (France)
3
School of Computing - Soongsil University, Séoul (Room #105, Information Science Building - Soongsil University, 511 - Sangdo-dong, Dongjak-gu - Seoul 156-743 - Korea - South Korea)
- Soongsil University, Seoul (France)
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^3 n) time algorithm to compute it.
Document type :
Conference papers
Complete list of metadatas
https://hal.inria.fr/inria-00189038
Contributor : Sylvain Lazard <>
Submitted on : Monday, November 19, 2007 - 6:56:33 PM
Last modification on : Friday, September 20, 2019 - 4:56:41 PM
Document(s) archivé(s) le : Monday, April 12, 2010 - 2:44:40 AM
Contributor : Sylvain Lazard <>
Submitted on : Monday, November 19, 2007 - 6:56:33 PM
Last modification on : Friday, September 20, 2019 - 4:56:41 PM
Document(s) archivé(s) le : Monday, April 12, 2010 - 2:44:40 AM
File
ESA.pdf
Files produced by the author(s)
Identifiers
- HAL Id : inria-00189038, version 1
- DOI : 10.1007/978-3-540-75520-3_37
Collections
INRIA | CNRS | LORIA | UNIV-LORRAINE
Citation
Otfried Cheong, Hazel Everett, Marc Glisse, Joachim Gudmundsson, Samuel Hornus, et al.. Farthest-Polygon Voronoi Diagrams. 15th Annual European Symposium on Algorithms - ALGO 2007, Oct 2007, Eilat, Israel. pp.407-418, ⟨10.1007/978-3-540-75520-3_37⟩. ⟨inria-00189038⟩
Metrics
Record views
371
Files downloads