A Simple Method for Avoiding Numerical Errors and Degeneracy in Voronoi Diagram Construction
Summary :
This paper presents a simple method for avoiding both numerical errors and degeneracy in an incremental-type algorithm for constructing the Voronoi diagram with respect to points on a plane. It is assumed that the coordinates of the given points are represented with a certain fixed number of bits. All the computations in the algorithm are carried out in four times higher precision, so that degeneracy can be discerned precisely. Every time degeneracy is found, the points are perturbed symbolically according to a very simple rule and thus are reduced to a nondegenerate case. The present technique makes a computer program simple in the sense that it avoids all numerical errors and requires no exceptional branches of processing for degenerate cases.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E75-A No.4 pp.468-477
- Publication Date
- 1992/04/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Issue on Discrete Mathematics and Its Application)
- 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
Kokichi SUGIHARA, "A Simple Method for Avoiding Numerical Errors and Degeneracy in Voronoi Diagram Construction" in IEICE TRANSACTIONS on Fundamentals,
vol. E75-A, no. 4, pp. 468-477, April 1992, doi: .
Abstract: This paper presents a simple method for avoiding both numerical errors and degeneracy in an incremental-type algorithm for constructing the Voronoi diagram with respect to points on a plane. It is assumed that the coordinates of the given points are represented with a certain fixed number of bits. All the computations in the algorithm are carried out in four times higher precision, so that degeneracy can be discerned precisely. Every time degeneracy is found, the points are perturbed symbolically according to a very simple rule and thus are reduced to a nondegenerate case. The present technique makes a computer program simple in the sense that it avoids all numerical errors and requires no exceptional branches of processing for degenerate cases.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e75-a_4_468/_p
Copy
@ARTICLE{e75-a_4_468,
author={Kokichi SUGIHARA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Simple Method for Avoiding Numerical Errors and Degeneracy in Voronoi Diagram Construction},
year={1992},
volume={E75-A},
number={4},
pages={468-477},
abstract={This paper presents a simple method for avoiding both numerical errors and degeneracy in an incremental-type algorithm for constructing the Voronoi diagram with respect to points on a plane. It is assumed that the coordinates of the given points are represented with a certain fixed number of bits. All the computations in the algorithm are carried out in four times higher precision, so that degeneracy can be discerned precisely. Every time degeneracy is found, the points are perturbed symbolically according to a very simple rule and thus are reduced to a nondegenerate case. The present technique makes a computer program simple in the sense that it avoids all numerical errors and requires no exceptional branches of processing for degenerate cases.},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - A Simple Method for Avoiding Numerical Errors and Degeneracy in Voronoi Diagram Construction
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 468
EP - 477
AU - Kokichi SUGIHARA
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E75-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 1992
AB - This paper presents a simple method for avoiding both numerical errors and degeneracy in an incremental-type algorithm for constructing the Voronoi diagram with respect to points on a plane. It is assumed that the coordinates of the given points are represented with a certain fixed number of bits. All the computations in the algorithm are carried out in four times higher precision, so that degeneracy can be discerned precisely. Every time degeneracy is found, the points are perturbed symbolically according to a very simple rule and thus are reduced to a nondegenerate case. The present technique makes a computer program simple in the sense that it avoids all numerical errors and requires no exceptional branches of processing for degenerate cases.
ER -
English
