Farthest-Polygon Voronoi Diagrams

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

inria-00442816, version 3

Farthest-Polygon Voronoi Diagrams

Otfried Cheong ¹, Hazel Everett ()^a^, 2, Marc Glisse ()^a^, 3, Joachim Gudmundsson ⁴, Samuel Hornus ( Auteur à contacter de préférence )^b^, 5, Sylvain Lazard ()^b^, 2, Mira Lee ¹, Hyeon-Suk Na ⁶

Computational Geometry 44, 4 (2011) 14 pages

Résumé : Given a family of k disjoint connected polygonal sites in general position and 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. We also prove a number of structural properties of this diagram. In particular, a Voronoi region may consist of k-1 connected components, but if one component is bounded, then it is equal to the entire region.

a – Université Nancy II
b – INRIA
1 : Department of Electrical Engineering [Korea Advanced Institute of Science and Technology] (KAIST)
Korea Advanced Institute of Science and Technology
2 : VEGAS (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
3 : GEOMETRICA (INRIA Sophia Antipolis / INRIA Saclay - Ile de France)
INRIA
4 : National ICT Australia (NICTA)
Australian National University – University of New South Wales – NSW Government – ACT Government
5 : ALICE (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
6 : School of Computing - Soongsil University, Séoul
Soongsil University, Seoul

inria-00442816, version 3
http://hal.inria.fr/inria-00442816
oai:hal.inria.fr:inria-00442816
Contributeur : Samuel Hornus <>
Soumis le : Lundi 29 Novembre 2010, 11:06:50
Dernière modification le : Mercredi 19 Janvier 2011, 15:11:53

Voir la fiche détaillée

Documents associés

PDF :

PS :

arXiv : 1001.3593

DOI : 10.1016/j.comgeo.2010.11.004

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="inria-00442816"><analytic>
<author><persName><forename>Otfried</forename><surname>Cheong</surname></persName>
<affiliation>
<orgName type="laboratory">KAIST</orgName>
<orgName type="team">Department of Electrical Engineering [Korea Advanced Institute of Science and Technology]</orgName>
<country>KR</country>
<orgName type="institution">Korea Advanced Institute of Science and Technology</orgName>
</affiliation>
</author>
<author><persName><forename>Hazel</forename><surname>Everett</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">VEGAS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Marc</forename><surname>Glisse</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis / INRIA Saclay - Ile de France</orgName>
<orgName type="team">GEOMETRICA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Joachim</forename><surname>Gudmundsson</surname></persName>
<affiliation>
<orgName type="laboratory">NICTA</orgName>
<orgName type="team">National ICT Australia</orgName>
<country>AU</country>
<orgName type="institution">Australian National University</orgName>
<orgName type="institution">University of New South Wales</orgName>
<orgName type="institution">NSW Government</orgName>
<orgName type="institution">ACT Government</orgName>
</affiliation>
</author>
<author><persName><forename>Samuel</forename><surname>Hornus</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">ALICE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Sylvain</forename><surname>Lazard</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">VEGAS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Mira</forename><surname>Lee</surname></persName>
<affiliation>
<orgName type="laboratory">KAIST</orgName>
<orgName type="team">Department of Electrical Engineering [Korea Advanced Institute of Science and Technology]</orgName>
<country>KR</country>
<orgName type="institution">Korea Advanced Institute of Science and Technology</orgName>
</affiliation>
</author>
<author><persName><forename>Hyeon-Suk</forename><surname>Na</surname></persName>
<affiliation>
<orgName type="team">School of Computing - Soongsil University, Séoul</orgName>
<country>KR</country>
<orgName type="institution">Soongsil University, Seoul</orgName>
</affiliation>
</author>
<title type="main" level="a">Farthest-Polygon Voronoi Diagrams</title></analytic><monogr><title level="j" type="main">Computational Geometry</title><imprint><publisher>Elsevier</publisher><biblScope type="publicationDate">2011-00-00</biblScope><biblScope type="vol">44</biblScope><biblScope type="issue">4</biblScope><biblScope type="pp">14 pages</biblScope></imprint></monogr><idno type="doi">10.1016/j.comgeo.2010.11.004</idno><idno type="HALid">http://hal.inria.fr/inria-00442816</idno><idno type="HALFile">http://hal.inria.fr/inria-00442816/PDF/final.pdf</idno></biblStruct>
</listBibl>
</listBibl>