ISSN:
1432-0541
Keywords:
Key words. Clipping a convex polyhedron, Line-segment Voronoi diagram, Robust implementation, Topological consistency.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. This paper presents an approach, called the ``topology-oriented approach,'' to numerically robust geometric algorithms. In this approach, the basic part of the algorithm is described in terms of combinatorial and topological computation primarily; this description guarantees robustness of the algorithm because combinatorial and topological computation is never contaminated with numerical errors. However, this part of the algorithm is usually nondeterministic, the flow of processing containing many alternative branches. Hence, numerical computation is used in order to choose the branch that seems the most promising to lead to the correct answer. The algorithm designed in this way is robust and simple. The basic idea of this approach as well as the basic properties of the resulting algorithms is shown with examples.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s004530010002
