Kurt
Mehlhorn
Max
Planck
Institute
for
Informatics
Reliable
and
Efficient
Geometric
Computing
Abstract: Reliable
implementation
of
geometric
algorithms
is
a
notoriously
difficult
task.
In
fact,
most
implementations
(academic
and
commercial)
of
geometric
algorithms
fail
on
some
input
instances,
i.e.,
crash
or
given
an
incorrect
answer.
In the introductory part of the talk, we illustrate the pitfalls of geometric computing [KMP+04] and explain for one algorithm in detail where the problem lies and what goes wrong. In the main part of the talk, we discuss a recent approach to reliable and efficient geometric computing: controlled perturbation. The approach was introduced by D. Halperin and co-workers [HS98, HR, HL04] and redefined by us [MOS, FKMS05]. We show that the approach applies to a large class of geometric algorithms, in particular, most algorithms in CGAL, [CGA], and yields correct and efficient implementations. The method is easy to use.