Mollified zone diagrams and their computation

Sergio C. De Biasi, Bahman Kalantari, Iraj Kalantari

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

8 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, Matoušek, and Tokuyama [1]. In this paper, we define mollified versions of zone diagram named territory diagram and maximal territory diagram. A zone diagram is a particular maximal territory diagram satisfying a sharp dominance property. The proof of existence of maximal territory diagrams depends on less restrictive initial conditions and is established via Zorn's lemma in contrast to the use of fixed-point theory in proving the existence of the zone diagram. Our proof of existence relies on a characterization which allows embedding any territory diagram into a maximal one. Our analysis of the structure of maximal territory diagrams is based on the introduction of a pair of dual concepts we call safe zone and forbidden zone. These in turn give rise to computational algorithms for the approximation of maximal territory diagrams. Maximal territory diagrams offer their own interesting theoretical and computational challenges, as well as insights into the structure of zone diagrams. This paper extends and updates previous work presented in [4].

Original languageEnglish (US)
Title of host publicationTransactions on Computational Science XIV - Special Issue on Voronoi Diagrams and Delaunay Triangulation
Pages31-59
Number of pages29
DOIs
StatePublished - Nov 25 2011
Event7th International Symposium on Voronoi Diagrams - Quebec City, QC, Canada
Duration: Jun 28 2010Jun 30 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6970 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other7th International Symposium on Voronoi Diagrams
CountryCanada
CityQuebec City, QC
Period6/28/106/30/10

Fingerprint

Diagram
Zorn's lemma
Euclidean plane
Fixed Point Theory
Voronoi Diagram
Computational Algorithm
Set of points
Finite Set
Initial conditions
Update
Approximation

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

De Biasi, S. C., Kalantari, B., & Kalantari, I. (2011). Mollified zone diagrams and their computation. In Transactions on Computational Science XIV - Special Issue on Voronoi Diagrams and Delaunay Triangulation (pp. 31-59). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6970 LNCS). https://doi.org/10.1007/978-3-642-25249-5_2
De Biasi, Sergio C. ; Kalantari, Bahman ; Kalantari, Iraj. / Mollified zone diagrams and their computation. Transactions on Computational Science XIV - Special Issue on Voronoi Diagrams and Delaunay Triangulation. 2011. pp. 31-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{bc9a888dc2f54b91bb434b351dd4b78c,
title = "Mollified 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, Matoušek, and Tokuyama [1]. In this paper, we define mollified versions of zone diagram named territory diagram and maximal territory diagram. A zone diagram is a particular maximal territory diagram satisfying a sharp dominance property. The proof of existence of maximal territory diagrams depends on less restrictive initial conditions and is established via Zorn's lemma in contrast to the use of fixed-point theory in proving the existence of the zone diagram. Our proof of existence relies on a characterization which allows embedding any territory diagram into a maximal one. Our analysis of the structure of maximal territory diagrams is based on the introduction of a pair of dual concepts we call safe zone and forbidden zone. These in turn give rise to computational algorithms for the approximation of maximal territory diagrams. Maximal territory diagrams offer their own interesting theoretical and computational challenges, as well as insights into the structure of zone diagrams. This paper extends and updates previous work presented in [4].",
author = "{De Biasi}, {Sergio C.} and Bahman Kalantari and Iraj Kalantari",
year = "2011",
month = "11",
day = "25",
doi = "10.1007/978-3-642-25249-5_2",
language = "English (US)",
isbn = "9783642252488",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "31--59",
booktitle = "Transactions on Computational Science XIV - Special Issue on Voronoi Diagrams and Delaunay Triangulation",

}

De Biasi, SC, Kalantari, B & Kalantari, I 2011, Mollified zone diagrams and their computation. in Transactions on Computational Science XIV - Special Issue on Voronoi Diagrams and Delaunay Triangulation. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6970 LNCS, pp. 31-59, 7th International Symposium on Voronoi Diagrams, Quebec City, QC, Canada, 6/28/10. https://doi.org/10.1007/978-3-642-25249-5_2

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

Transactions on Computational Science XIV - Special Issue on Voronoi Diagrams and Delaunay Triangulation. 2011. p. 31-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6970 LNCS).

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

TY - GEN

T1 - Mollified zone diagrams and their computation

AU - De Biasi, Sergio C.

AU - Kalantari, Bahman

AU - Kalantari, Iraj

PY - 2011/11/25

Y1 - 2011/11/25

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, Matoušek, and Tokuyama [1]. In this paper, we define mollified versions of zone diagram named territory diagram and maximal territory diagram. A zone diagram is a particular maximal territory diagram satisfying a sharp dominance property. The proof of existence of maximal territory diagrams depends on less restrictive initial conditions and is established via Zorn's lemma in contrast to the use of fixed-point theory in proving the existence of the zone diagram. Our proof of existence relies on a characterization which allows embedding any territory diagram into a maximal one. Our analysis of the structure of maximal territory diagrams is based on the introduction of a pair of dual concepts we call safe zone and forbidden zone. These in turn give rise to computational algorithms for the approximation of maximal territory diagrams. Maximal territory diagrams offer their own interesting theoretical and computational challenges, as well as insights into the structure of zone diagrams. This paper extends and updates previous work presented in [4].

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, Matoušek, and Tokuyama [1]. In this paper, we define mollified versions of zone diagram named territory diagram and maximal territory diagram. A zone diagram is a particular maximal territory diagram satisfying a sharp dominance property. The proof of existence of maximal territory diagrams depends on less restrictive initial conditions and is established via Zorn's lemma in contrast to the use of fixed-point theory in proving the existence of the zone diagram. Our proof of existence relies on a characterization which allows embedding any territory diagram into a maximal one. Our analysis of the structure of maximal territory diagrams is based on the introduction of a pair of dual concepts we call safe zone and forbidden zone. These in turn give rise to computational algorithms for the approximation of maximal territory diagrams. Maximal territory diagrams offer their own interesting theoretical and computational challenges, as well as insights into the structure of zone diagrams. This paper extends and updates previous work presented in [4].

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

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

U2 - 10.1007/978-3-642-25249-5_2

DO - 10.1007/978-3-642-25249-5_2

M3 - Conference contribution

SN - 9783642252488

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 31

EP - 59

BT - Transactions on Computational Science XIV - Special Issue on Voronoi Diagrams and Delaunay Triangulation

ER -

De Biasi SC, Kalantari B, Kalantari I. Mollified zone diagrams and their computation. In Transactions on Computational Science XIV - Special Issue on Voronoi Diagrams and Delaunay Triangulation. 2011. p. 31-59. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-25249-5_2