Cours de robustesse a Nancy

Sylvain Pion

Informations

• Publié par: Dafeg
• Nombre de lectures: 11
• Langue: English

Extrait

Robustness issues in CGAL :
arithmetics and the kernel
Sylvain Pion
INRIA Sophia AntipolisPlan
Links between geometry and arithmetics
Floating point arithmetic
Exact arithmetic
Arithmetic lters
CGAL implementation
1Introduction
2Examples of geometric predicates
positive
C1orientation p
q
C2 C’1r p’
C’2
p negative
orientation
x(p) <? x(p’) x
orientation(p,q,r) =
sign((x(p) x(r))(y(q) y(r)) (x(q) x(r))(y(p) y(r)))
Predicate of degree 2.
Sylvain Pion 3Examples of geometric constructions
y
p C1
p
y(p)
C2
c r
q
O x(p) x
Sylvain Pion 4From geometry to arithmetic
Geometric algorithm
⇒ Geometric operations (predicates and constructions)
⇒ Algebraic operations over coordinates/coe cients
√
⇒ Arithmetic operations (+, ,,, ...)
Sylvain Pion 5Arithmetic ⇒ Geometry
Cost of arithmetic⇒ Time complexity of geometric algorithms
Approximate arithmetic⇒ robustness problems of geometric algorithms
Sylvain Pion 6The Real-RAM model
Real computer model with random access (RAM = Random access machine).
Theoretical model specifying the behavior of real arithmetic on computers.
All arithmetic operations over reals cost O(1) time (and are exact).
All real variables take O(1) memory space.
Complexity analyses of geometric algorithms are traditionnaly performed within
this model.
Sylvain Pion 7Relationship with the reality of computers ?
Two approaches :
Floating point arithmetic, approximate.
Exact arithmetic, slower.
For geometry : which approach is the best in practice ?
What is the precise cost of the exact approach ?
8Floating point arithmetic
9