Farthest-polygon Voronoi diagrams

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

doi:10.1016/j.comgeo.2010.11.004

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
Nancy Université
INRIA
Commonwealth Scientific and Industrial Research Organization
LORIA Laboratoire Lorrain de Recherche en Informatique et ses Applications
Soongsil University

Research output: Contribution to journal › Article › peer-review

Abstract

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(nlog ³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.

Original language	English
Pages (from-to)	234-247
Number of pages	14
Journal	Computational Geometry: Theory and Applications
Volume	44
Issue number	4
DOIs	https://doi.org/10.1016/j.comgeo.2010.11.004
Publication status	Published - 1 Jan 2011
Externally published	Yes

Keywords

Voronoi diagram

Access to Document

10.1016/j.comgeo.2010.11.004

Cite this

@article{d7a5a63824be41659e5e4c3253076aa1,

title = "Farthest-polygon Voronoi diagrams",

abstract = "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(nlog 3n) 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.",

keywords = "Voronoi diagram",

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 = "2011",

month = jan,

day = "1",

doi = "10.1016/j.comgeo.2010.11.004",

language = "English",

volume = "44",

pages = "234--247",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

number = "4",

}

TY - JOUR

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 - 2011/1/1

Y1 - 2011/1/1

N2 - 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(nlog 3n) 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.

AB - 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(nlog 3n) 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.

KW - Voronoi diagram

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

U2 - 10.1016/j.comgeo.2010.11.004

DO - 10.1016/j.comgeo.2010.11.004

M3 - Article

AN - SCOPUS:78751642319

SN - 0925-7721

VL - 44

SP - 234

EP - 247

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 4

ER -

Farthest-polygon Voronoi diagrams

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this