Robustness and degeneracies

Computational geometry algorithms had some difficulties to go from theory to practice. The main reason is that algorithms are designed in the context of real Euclidean geometry. That is, mathematical and geometrical theorems are assumed to be true. But unfortunately, they are false in the computer, because the computer does not know how to represent real numbers and makes only rounded computations.

Combinatorics and predicates

Most algorithms are combinatorial, the computed information is of discrete nature, for example, given a set of points we are looking for an order among these points (sorting), a subset of the points (convex hull) or triples formed by these points (Delaunay triangulation).

To take decisions, the combinatorial algorithm asks elementary geometric questions called predicates, for example, comparison of abscissae of two points, orientation of a triangle defined by three points or side of a point with respect to a circle through three other points.


Geometric coherence

Problems come from the fact that the answers to different predicates are incoherent.

Example: turn around v

t=t0
do
  let vpq vertices of t ccw
  t = neighbor of t through qv
while t not equal to t0

This piece of code traverse the triangles incident to v in a triangulation. The computation of the next triangle rely on an orientation test, an error in that test will put the code in an infinite loop (see figure).

We start at triangle t0=vr1r2=vpq
we go to neighbor vr2r3=vpq
then to neighbor vr4r3=vpq with an orientation error there
The code loops between vr2r3 and vr4r3

This result is incoherent since from the orientation tests r2 and r4 are on the same side of edge vr3 which is impossible since both triangles vr2r3 and vr4r3 exist in the triangulation.


Solutions

Incoherences may come from rounding errors in predicates evaluation. Using exact arithmetics and other tools yields to efficient exact predicates and thus coherent.

Predicates have usually three answers, two main answers (inside, outside) and some "limit" answer in between (on the boundary). We say that the configuration is degenerate. Many algorithms do not take in account degeneracies, they can be solved by the use of technics simulating non degeneracies: predicates never answer that the configuration is degenerate, they always choose between one of the two main answers; but these choices must be coherent together.


Last modified: Tue Apr 11 10:08:13 MET DST 2000 Olivier Devillers Topics PRISME Homepage la même page en français