./Overview.nw1Let li have the line equation ai x + bi y + ci = 0. The intersection point is the solution of a system of two linear equations of two unknowns and hence we have (I might have gotten the sign incorrect for the c-entries in the numerator)
be any real number within the range
of normalized flaoting point numbers and let
be the closest
floating point number. We claim
If z is a representable number, there is nothing to show. Otherwise,
Briefly review interval arithmetic with endpoint representation; mention that it is costly; about triples the cost; also requires to change rounding mode.
end of lecture, Thursday, November 8
Lecture on Tuesday, November 13
put theorems 1 and 2 of handout on the board.
apply to orientation predicate as discussed on page 615 of LEDAbook and on page 4 of handout. Show the actual LEDA code.
Discuss the code. Show how the orientation formula is obtained from the formula for the cartesian coordinates. Emphasize that is was done in a stupid way. Challenge a student to go through the geometry kernel and improve it. Tell them that we have roundoff error. Assume that our number have homogeneous coordinates between 0 and 216. Let L = 16. Then E might be as large as 24L +3 = 267 and hence cannot be presented exactly by a floating point number. In fact, the last 15 bits might be missing. Due to intermediate rounding even more bits might be missing. Theorem 1 tells you exactly, how large the error might be. Namely, as large as .
Show slides on effectiveness of floating point filter. Do it with and without the improved determinant formula. I checked the LEDA implementation. We are already using the improved formulae. The numbers for the old kernel are in my talk for Leiden. Also show that robustness is not an academic problem.
Prove the theorems.
The art of floating point filters was considerably refined by Christoph Burnikel, Stefan Funke, Sylvain Pion and others [BFS98,Fun97,BBP98].