On Linear-Sized Farthest-Color Voronoi Diagrams
Summary :
Given a collection of k sets consisting of a total of n points in the plane, the distance from any point in the plane to each of the sets is defined to be the minimum among distances to each point in the set. The farthest-color Voronoi diagram is defined as a generalized Voronoi diagram of the k sets with respect to the distance functions for each of the k sets. The combinatorial complexity of the diagram is known to be Θ(kn) in the worst case. This paper initiates a study on farthest-color Voronoi diagrams having O(n) complexity. We introduce a realistic model, which defines a certain class of the diagrams with desirable geometric properties observed. We finally show that the farthest-color Voronoi diagrams under the model have linear complexity.
- Publication
- IEICE TRANSACTIONS on Information Vol.E95-D No.3 pp.731-736
- Publication Date
- 2012/03/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E95.D.731
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science – Mathematical Foundations and Applications of Computer Science and Algorithms –)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Sang Won BAE, "On Linear-Sized Farthest-Color Voronoi Diagrams" in IEICE TRANSACTIONS on Information,
vol. E95-D, no. 3, pp. 731-736, March 2012, doi: 10.1587/transinf.E95.D.731.
Abstract: Given a collection of k sets consisting of a total of n points in the plane, the distance from any point in the plane to each of the sets is defined to be the minimum among distances to each point in the set. The farthest-color Voronoi diagram is defined as a generalized Voronoi diagram of the k sets with respect to the distance functions for each of the k sets. The combinatorial complexity of the diagram is known to be Θ(kn) in the worst case. This paper initiates a study on farthest-color Voronoi diagrams having O(n) complexity. We introduce a realistic model, which defines a certain class of the diagrams with desirable geometric properties observed. We finally show that the farthest-color Voronoi diagrams under the model have linear complexity.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E95.D.731/_p
Copy
@ARTICLE{e95-d_3_731,
author={Sang Won BAE, },
journal={IEICE TRANSACTIONS on Information},
title={On Linear-Sized Farthest-Color Voronoi Diagrams},
year={2012},
volume={E95-D},
number={3},
pages={731-736},
abstract={Given a collection of k sets consisting of a total of n points in the plane, the distance from any point in the plane to each of the sets is defined to be the minimum among distances to each point in the set. The farthest-color Voronoi diagram is defined as a generalized Voronoi diagram of the k sets with respect to the distance functions for each of the k sets. The combinatorial complexity of the diagram is known to be Θ(kn) in the worst case. This paper initiates a study on farthest-color Voronoi diagrams having O(n) complexity. We introduce a realistic model, which defines a certain class of the diagrams with desirable geometric properties observed. We finally show that the farthest-color Voronoi diagrams under the model have linear complexity.},
keywords={},
doi={10.1587/transinf.E95.D.731},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - On Linear-Sized Farthest-Color Voronoi Diagrams
T2 - IEICE TRANSACTIONS on Information
SP - 731
EP - 736
AU - Sang Won BAE
PY - 2012
DO - 10.1587/transinf.E95.D.731
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E95-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2012
AB - Given a collection of k sets consisting of a total of n points in the plane, the distance from any point in the plane to each of the sets is defined to be the minimum among distances to each point in the set. The farthest-color Voronoi diagram is defined as a generalized Voronoi diagram of the k sets with respect to the distance functions for each of the k sets. The combinatorial complexity of the diagram is known to be Θ(kn) in the worst case. This paper initiates a study on farthest-color Voronoi diagrams having O(n) complexity. We introduce a realistic model, which defines a certain class of the diagrams with desirable geometric properties observed. We finally show that the farthest-color Voronoi diagrams under the model have linear complexity.
ER -
English
