Two design principles of geometric algorithms in finite-precision arithmetic (Q749243)

Geometric algorithms are usually designed in the world where no numerical error exists. However, in real computers, every real number is represented in finite precision, so that straightforward translation of a geometric algorithm into a programming language will not necessarily give a practical computer program. Thus, there is a gap between ``theoretically correct'' algorithms and ``practically valid'' computer programs. The authors present two approaches for filling the gap. The first approach is to construct a closed world in which topological structures of geometric objects are determined precisely. The second approach is to avoid topological inconsistency by placing higher priority to logical consequence than to numerical judgement; this approach is applied to the construction of Voronoi diagrams.