The LEDA Geometry Kernel, 3 Lectures

1.

handouts: chapter 9 of LEDA book (geometry kernels), improved write-up of floating point filter.

2.

representation of points, lines, segments, cartesian and homogenous coordinates; it is natural to represent points by their coordinates. For points constructed during the course of a computation, this is not the only representation. A ``more geometric'' representation may be advantageous. See below.

3.

number types: float, double, integer, float incurs round-off error

4.

evaluation of geometric predicates = sign of arithmetic expression, discuss orientation predicate,

5.

dangers of floating point arithmetic, point them to braided lines in LEDAbook, show points of lines. Discuss in detail what happens when we compute the intersection of two lines and test whether the point of intersection is contained in the first line.

./Overview.nw1Let l_i have the line equation a_i x + b_i y + c_i = 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)

$$x_p = \frac{ \left\Lvert\begin{array}{cc} c_1 & b_1 \\ c_2... ...array}{cc} a_1 & b_1 \\ a_2 & b_2 \end{array}\right\Lvert$$

and similarly for y_p. The two lines are parallel, if D = 0. If the lines are not parallel, the test whether p lies on l1 amonts to the test a₁ x_p + b₁ y_p + c₁ = 0.

6.

properties of flaoting point numbers, pages 616 to 618 of LEDAbook, introduce MINNORM and MAXDOUBLE and prove that the statement about the round-off error for any real between MINNORM and MAXDOUBLE. Let MINNORM be the smallest normalized floating point number, i.e.,

$${\tt MINNORM} = 1 2^{1 - 1023} = 2^{-1022} \ .$$

Let ${\tt MINNORM} \le z \le {\tt MAXDOUBLE}$ be any real number within the range of normalized flaoting point numbers and let $\tilde{z}$ be the closest floating point number. We claim

$$\vert z - \tilde{z} \vert \le 2^{-53} \min(z,\tilde{z}) \ .$$

If z is a representable number, there is nothing to show. Otherwise,

$$z = ( 1 + \sum_{i \ge 1} m_i 2^{-i} ) 2^{e - 1023}$$

with $1 \le e < 2046$, i.e., e is smaller than the maximal possible value. The numbers

$$z^- = ( ( 1 + \sum_{1 \le i \le 52} m_i 2^{-i} ) 2^{e - 1023}... ...= 1 + \sum_{1 \le i \le 52} m_i 2^{-i} + 2^{-52}) 2^{e - 1023}$$

are both representable and $\tilde{z}$ is the one closer to z. Thus

$$\vert z - \tilde{z} \vert \le 2^{-53} 2^{e - 1023} \le 2^{-53} \min(z,\tilde{z}) \ .$$

7.

floating point filters, we need to compute an interval containing E. The simplest way to do so is interval arithmetic. Intervals can be represented by endpoints or by centerpoint and radius.

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 2¹⁶. Let L = 16. Then E might be as large as 2^{4L +3} = 2⁶⁷ 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 $11\cdot 2^{67}$.

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].