Effective Computational Geometry for Curves and Surfaces

Creditpoints: 9 | |

Class: Tuesday and Thursday, 11.00 - 13.00, | |

at the MPI (Building 46), Room 024 | |

Exercises: Wednesday, 16.00 - 18.00, | |

at the Mathematics Department (Building 27.2), Room ZS (Zeichensaal) |

In the lecture we address common problems in the implementation of algorithms in computational geometry, in particular, new questions when known methods for segments and lines are extended to curves and surfaces. We start with the traditional sweep-line algorithm and randomized- incremental construction. We discuss

arithmetic precision, separation bounds | |

floating point filters, | |

computation with algebraic numbers, | |

curves and curve arrangements, | |

quadric surfaces and surface arrangements, | |

software structure of LEDA and CGAL, | |

C++ techniques. |

Our final goal is the development of data structures and of efficient and exact algorithms for boolean operations on curved polygons and curved polyhedra. Examples can be seen in the ongoing project EXACUS (Efficient and Exact Algorithms for Curves and Surfaces) at the MPII. In the continuation of the course we offer Fopra's and Thesis on theses topics.

- LEDAbook Section 10.7, Line Segment Intersection
- Raimund Seidel, Backwards Analysis of Randomized Geometric Algorithms
- Stefan Schirra, A Case Study on the Cost of Geometric Computing
- LEDAbook Chapter 9, Geometry Kernels
- Proofs for algebraic numbers
- Remark on floating point arithmetik
- LEDA reals
- separation bound for real algebraic expressions (there is a mistake in the paper: u(E) is wrong for the diamond operator, the version in the lecture was correct)
- diamond operator
- Termination proof for Uspensky
- Proof for Sturm sequences
- E. Berberich et al., A computational basis for conic arcs and boolean operations on conic polygons
- Jacobi curves
- References for Nef-Polyhedra

Lutz Kettner
(*<surname>*@mpi-inf.mpg.de).
Last modified on Tuesday, 17-Jan-2006 17:53:31 MET.