Robust Geometric Computation Based on Digital Topology

Abstract

This paper presents a new scheme for designing numerically robust geometric algorithms based on topological consistency. The topology-based approach is one of the most successful principle for designing robust algorithms to solve geometric problems, which the author’s group has been developed for a long time. This approach generates efficient algorithms because the floating-point arithmetic can be used, but is not a beginners’ technique because topological invariants for individual problems are required in the design of the algorithms. The new scheme presented here uses digital topology instead of individual invariants, and hence will change the topology-based approach from a middle-level technique to a beginners’ level technique. The basic idea together with its application to wire bundling is presented.