Maximal zone diagrams and their computation

Sergio C. De Biasi, Bahman Kalantari, Iraj Kalantari

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Citations (Scopus)

Abstract

The notion of the "zone diagram" of a finite set of points in the Euclidean plane is an interesting and rich variation of the classical Voronoi diagram, introduced by Asano, Matousek, Tokuyama [1]. Here, we define the more inclusive notion of a "maximal zone diagram". The proof of existence of maximal zone diagrams depends on less restrictive initial conditions and is thus conveniently established via Zorn's lemma in contrast to the use of fixed-point theory in proving the existence of a unique zone diagram. A zone diagram is a particular maximal zone diagram satisfying a unique dominance property. We give a characterization for maximal zone diagrams which allows recognition of maximality of certain subsets called "subzone diagrams", as well as that of their iterative improvement toward maximality. Maximal zone diagrams offer their own interesting theoretical and computational challenges.

Original languageEnglish (US)
Title of host publicationISVD 2010 - 7th International Symposium on Voronoi Diagrams in Science and Engineering
Pages171-180
Number of pages10
DOIs
StatePublished - Aug 23 2010
Event7th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2010 - Quebec City, QC, Canada
Duration: Jun 28 2010Jun 30 2010

Publication series

NameISVD 2010 - 7th International Symposium on Voronoi Diagrams in Science and Engineering

Other

Other7th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2010
CountryCanada
CityQuebec City, QC
Period6/28/106/30/10

Fingerprint

Diagram
Zorn's lemma
Euclidean plane
Fixed Point Theory
Voronoi Diagram
Set of points
Finite Set
Initial conditions
Subset

All Science Journal Classification (ASJC) codes

  • Applied Mathematics
  • Discrete Mathematics and Combinatorics

Keywords

  • Computational geometry.
  • Voronoi diagram
  • Zone diagram
  • Zorn's lemma

Cite this

De Biasi, S. C., Kalantari, B., & Kalantari, I. (2010). Maximal zone diagrams and their computation. In ISVD 2010 - 7th International Symposium on Voronoi Diagrams in Science and Engineering (pp. 171-180). [5521422] (ISVD 2010 - 7th International Symposium on Voronoi Diagrams in Science and Engineering). https://doi.org/10.1109/ISVD.2010.10
De Biasi, Sergio C. ; Kalantari, Bahman ; Kalantari, Iraj. / Maximal zone diagrams and their computation. ISVD 2010 - 7th International Symposium on Voronoi Diagrams in Science and Engineering. 2010. pp. 171-180 (ISVD 2010 - 7th International Symposium on Voronoi Diagrams in Science and Engineering).
@inproceedings{b983771f743c4731828e8f7bec9ce596,
title = "Maximal zone diagrams and their computation",
abstract = "The notion of the {"}zone diagram{"} of a finite set of points in the Euclidean plane is an interesting and rich variation of the classical Voronoi diagram, introduced by Asano, Matousek, Tokuyama [1]. Here, we define the more inclusive notion of a {"}maximal zone diagram{"}. The proof of existence of maximal zone diagrams depends on less restrictive initial conditions and is thus conveniently established via Zorn's lemma in contrast to the use of fixed-point theory in proving the existence of a unique zone diagram. A zone diagram is a particular maximal zone diagram satisfying a unique dominance property. We give a characterization for maximal zone diagrams which allows recognition of maximality of certain subsets called {"}subzone diagrams{"}, as well as that of their iterative improvement toward maximality. Maximal zone diagrams offer their own interesting theoretical and computational challenges.",
keywords = "Computational geometry., Voronoi diagram, Zone diagram, Zorn's lemma",
author = "{De Biasi}, {Sergio C.} and Bahman Kalantari and Iraj Kalantari",
year = "2010",
month = "8",
day = "23",
doi = "10.1109/ISVD.2010.10",
language = "English (US)",
isbn = "9780769541129",
series = "ISVD 2010 - 7th International Symposium on Voronoi Diagrams in Science and Engineering",
pages = "171--180",
booktitle = "ISVD 2010 - 7th International Symposium on Voronoi Diagrams in Science and Engineering",

}

De Biasi, SC, Kalantari, B & Kalantari, I 2010, Maximal zone diagrams and their computation. in ISVD 2010 - 7th International Symposium on Voronoi Diagrams in Science and Engineering., 5521422, ISVD 2010 - 7th International Symposium on Voronoi Diagrams in Science and Engineering, pp. 171-180, 7th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2010, Quebec City, QC, Canada, 6/28/10. https://doi.org/10.1109/ISVD.2010.10

Maximal zone diagrams and their computation. / De Biasi, Sergio C.; Kalantari, Bahman; Kalantari, Iraj.

ISVD 2010 - 7th International Symposium on Voronoi Diagrams in Science and Engineering. 2010. p. 171-180 5521422 (ISVD 2010 - 7th International Symposium on Voronoi Diagrams in Science and Engineering).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Maximal zone diagrams and their computation

AU - De Biasi, Sergio C.

AU - Kalantari, Bahman

AU - Kalantari, Iraj

PY - 2010/8/23

Y1 - 2010/8/23

N2 - The notion of the "zone diagram" of a finite set of points in the Euclidean plane is an interesting and rich variation of the classical Voronoi diagram, introduced by Asano, Matousek, Tokuyama [1]. Here, we define the more inclusive notion of a "maximal zone diagram". The proof of existence of maximal zone diagrams depends on less restrictive initial conditions and is thus conveniently established via Zorn's lemma in contrast to the use of fixed-point theory in proving the existence of a unique zone diagram. A zone diagram is a particular maximal zone diagram satisfying a unique dominance property. We give a characterization for maximal zone diagrams which allows recognition of maximality of certain subsets called "subzone diagrams", as well as that of their iterative improvement toward maximality. Maximal zone diagrams offer their own interesting theoretical and computational challenges.

AB - The notion of the "zone diagram" of a finite set of points in the Euclidean plane is an interesting and rich variation of the classical Voronoi diagram, introduced by Asano, Matousek, Tokuyama [1]. Here, we define the more inclusive notion of a "maximal zone diagram". The proof of existence of maximal zone diagrams depends on less restrictive initial conditions and is thus conveniently established via Zorn's lemma in contrast to the use of fixed-point theory in proving the existence of a unique zone diagram. A zone diagram is a particular maximal zone diagram satisfying a unique dominance property. We give a characterization for maximal zone diagrams which allows recognition of maximality of certain subsets called "subzone diagrams", as well as that of their iterative improvement toward maximality. Maximal zone diagrams offer their own interesting theoretical and computational challenges.

KW - Computational geometry.

KW - Voronoi diagram

KW - Zone diagram

KW - Zorn's lemma

UR - http://www.scopus.com/inward/record.url?scp=77955686017&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955686017&partnerID=8YFLogxK

U2 - 10.1109/ISVD.2010.10

DO - 10.1109/ISVD.2010.10

M3 - Conference contribution

AN - SCOPUS:77955686017

SN - 9780769541129

T3 - ISVD 2010 - 7th International Symposium on Voronoi Diagrams in Science and Engineering

SP - 171

EP - 180

BT - ISVD 2010 - 7th International Symposium on Voronoi Diagrams in Science and Engineering

ER -

De Biasi SC, Kalantari B, Kalantari I. Maximal zone diagrams and their computation. In ISVD 2010 - 7th International Symposium on Voronoi Diagrams in Science and Engineering. 2010. p. 171-180. 5521422. (ISVD 2010 - 7th International Symposium on Voronoi Diagrams in Science and Engineering). https://doi.org/10.1109/ISVD.2010.10