On properties of forbidden zones of polygons and polytopes

Ross Berkowitz, Bahman Kalantari, Iraj Kalantari, David Menendez

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

1 Citation (Scopus)

Abstract

Given a region R in a Euclidean space and a distinguished point p â̂̂ R, the forbidden zone, F(R,p), is the union of all open balls with center in R having p as a common boundary point. The notion of forbidden zone, defined in [2], was shown to be instrumental in the characterization of mollified zone diagrams, a relaxation of zone diagrams, introduced by Asano, et al. [3], itself a variation of Voronoi diagrams. For a polygon P, we derive formulas for the area and circumference of F(P,p) when p is fixed, and for minimum areas and circumferences when p ranges in P. These optimizations associate interesting new centers to P, even when a triangle. We give some extensions to polytopes and bounded convex sets. We generalize forbidden zones by allowing p to be replaced by an arbitrary subset, with attention to the case of finite sets. The corresponding optimization problems, even for two-point sites, and their characterizations result in many new and challenging open problems.

Original languageEnglish (US)
Title of host publicationTransactions on Computational Science XX
Subtitle of host publicationSpecial Issue on Voronoi Diagrams and Their Applications
Pages112-137
Number of pages26
DOIs
StatePublished - Dec 1 2013

Publication series

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

Fingerprint

Polytopes
Polygon
Circumference
Diagram
Voronoi Diagram
Bounded Set
Convex Sets
Euclidean space
Finite Set
Triangle
Open Problems
Ball
Union
Optimization Problem
Generalise
Subset
Optimization
Arbitrary
Range of data

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Berkowitz, R., Kalantari, B., Kalantari, I., & Menendez, D. (2013). On properties of forbidden zones of polygons and polytopes. In Transactions on Computational Science XX: Special Issue on Voronoi Diagrams and Their Applications (pp. 112-137). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8110). https://doi.org/10.1007/978-3-642-41905-8-8
Berkowitz, Ross ; Kalantari, Bahman ; Kalantari, Iraj ; Menendez, David. / On properties of forbidden zones of polygons and polytopes. Transactions on Computational Science XX: Special Issue on Voronoi Diagrams and Their Applications. 2013. pp. 112-137 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{42c44b0382854988ae91925c68877c01,
title = "On properties of forbidden zones of polygons and polytopes",
abstract = "Given a region R in a Euclidean space and a distinguished point p {\^a}̂̂ R, the forbidden zone, F(R,p), is the union of all open balls with center in R having p as a common boundary point. The notion of forbidden zone, defined in [2], was shown to be instrumental in the characterization of mollified zone diagrams, a relaxation of zone diagrams, introduced by Asano, et al. [3], itself a variation of Voronoi diagrams. For a polygon P, we derive formulas for the area and circumference of F(P,p) when p is fixed, and for minimum areas and circumferences when p ranges in P. These optimizations associate interesting new centers to P, even when a triangle. We give some extensions to polytopes and bounded convex sets. We generalize forbidden zones by allowing p to be replaced by an arbitrary subset, with attention to the case of finite sets. The corresponding optimization problems, even for two-point sites, and their characterizations result in many new and challenging open problems.",
author = "Ross Berkowitz and Bahman Kalantari and Iraj Kalantari and David Menendez",
year = "2013",
month = "12",
day = "1",
doi = "10.1007/978-3-642-41905-8-8",
language = "English (US)",
isbn = "9783642419041",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "112--137",
booktitle = "Transactions on Computational Science XX",

}

Berkowitz, R, Kalantari, B, Kalantari, I & Menendez, D 2013, On properties of forbidden zones of polygons and polytopes. in Transactions on Computational Science XX: Special Issue on Voronoi Diagrams and Their Applications. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8110, pp. 112-137. https://doi.org/10.1007/978-3-642-41905-8-8

On properties of forbidden zones of polygons and polytopes. / Berkowitz, Ross; Kalantari, Bahman; Kalantari, Iraj; Menendez, David.

Transactions on Computational Science XX: Special Issue on Voronoi Diagrams and Their Applications. 2013. p. 112-137 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8110).

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

TY - GEN

T1 - On properties of forbidden zones of polygons and polytopes

AU - Berkowitz, Ross

AU - Kalantari, Bahman

AU - Kalantari, Iraj

AU - Menendez, David

PY - 2013/12/1

Y1 - 2013/12/1

N2 - Given a region R in a Euclidean space and a distinguished point p â̂̂ R, the forbidden zone, F(R,p), is the union of all open balls with center in R having p as a common boundary point. The notion of forbidden zone, defined in [2], was shown to be instrumental in the characterization of mollified zone diagrams, a relaxation of zone diagrams, introduced by Asano, et al. [3], itself a variation of Voronoi diagrams. For a polygon P, we derive formulas for the area and circumference of F(P,p) when p is fixed, and for minimum areas and circumferences when p ranges in P. These optimizations associate interesting new centers to P, even when a triangle. We give some extensions to polytopes and bounded convex sets. We generalize forbidden zones by allowing p to be replaced by an arbitrary subset, with attention to the case of finite sets. The corresponding optimization problems, even for two-point sites, and their characterizations result in many new and challenging open problems.

AB - Given a region R in a Euclidean space and a distinguished point p â̂̂ R, the forbidden zone, F(R,p), is the union of all open balls with center in R having p as a common boundary point. The notion of forbidden zone, defined in [2], was shown to be instrumental in the characterization of mollified zone diagrams, a relaxation of zone diagrams, introduced by Asano, et al. [3], itself a variation of Voronoi diagrams. For a polygon P, we derive formulas for the area and circumference of F(P,p) when p is fixed, and for minimum areas and circumferences when p ranges in P. These optimizations associate interesting new centers to P, even when a triangle. We give some extensions to polytopes and bounded convex sets. We generalize forbidden zones by allowing p to be replaced by an arbitrary subset, with attention to the case of finite sets. The corresponding optimization problems, even for two-point sites, and their characterizations result in many new and challenging open problems.

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

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

U2 - 10.1007/978-3-642-41905-8-8

DO - 10.1007/978-3-642-41905-8-8

M3 - Conference contribution

SN - 9783642419041

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

SP - 112

EP - 137

BT - Transactions on Computational Science XX

ER -

Berkowitz R, Kalantari B, Kalantari I, Menendez D. On properties of forbidden zones of polygons and polytopes. In Transactions on Computational Science XX: Special Issue on Voronoi Diagrams and Their Applications. 2013. p. 112-137. (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-41905-8-8