Combinatorics and predicatesMost 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 coherenceProblems come from the fact that the answers to different predicates are incoherent.
Example: turn around vt=t0
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
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.
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|