Reliable Geometric Computation via Controlled Perturbation !?

task. Algorithms are usually designed for the Real-RAM, capable of computing
with real numbers in the sense of mathematics, and for
non-degenerate inputs. But, real
computers are not Real-RAMs and inputs are frequently degenerate.

In the first part of the talk we illustrate the pitfalls of geometric
computing by way of examples~\cite{ClassRoomExample}. The examples demonstrate
in a lucid way that standard and frequently taught algorithms can go completely
astray when naively implemented with floating point arithmetic.



In the second part of the talk, we discuss approaches to reliable and efficient
geometric computing, in particular the controlled or active perturbation
approach introduced by D.~Halperin and
co-workers~\cite{Halperin-Shelton:perturbation,Halperin-Raab:perturbation,Halperin-Leiserowitz}.
It proposes to slightly perturb the given
input in a carefully chosen way so as to avoid degeneracies and so as to reduce
the arithmetic demand. The exact solution on the perturbed input (not the
original input!) is then computed. The scheme only applies when
an approximate result suffices. This is the case whenever inputs are only
approximately known.


We build on the work of Halperin~et.~al.~and show that controlled perturbation
is a general and simple
technique for making a large class
of geometric algorithms reliable. We also quantify the relation between the
amount of perturbation and the precision of the floating point system. We
exemplify the method on
examples.

Zuerich next month.