Campus Event Calendar
Event Entry
New for: D2, D3
What and Who
Exact Geometric Computing - From Numerical Analysis to Algebraic Geometry
Michael Sagraloff
Max-Planck-Institut für Informatik - D1
Joint MPI-INF/MPI-SWS Lecture Series
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI
MPI Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 2 November 2011
12:15
60 Minutes
E1 4
024
Saarbrücken
Abstract
Computing with geometric objects (lines, planes, circles, ellipses, Bezier curves, etc.) constitutes a fundamental task in many areas such as robot motion planning, geometric modeling and computer aided design. Geometric algorithms are typically formulated under the assumption that all computations are carried out exactly, whereas actual implementations exclusively rely on floating point arithmetic. As a consequence, predicates are wrongly evaluated due to rounding errors which, in turn, leads to false results, crashes or non-terminating programs. In the first part of the talk, I will illustrate the latter fact by means of a simple example showing that there is a need for algorithms that can process any given input (complete) and, in addition, come with a guarantee on the exactness of the result (exact).
An important subtask for many geometric algorithms is the computation of arrangements of (semi-)algebraic curves and surfaces. Computing such arrangements in an exact manner constitutes a difficult problem. This is mainly due to the fact that solutions of polynomial systems must be found and further processed, and the corresponding operations are computationally intensive. In the second part of the talk, I will outline how to improve the overall efficiency of such computations by combining techniques from different fields such as numerical analysis, computer algebra and algebraic geometry.
I will also report on recent algorithms that have been integrated in the computational geometry algorithms library (CGAL) and theoretical results which have been achieved during the last years.
An important subtask for many geometric algorithms is the computation of arrangements of (semi-)algebraic curves and surfaces. Computing such arrangements in an exact manner constitutes a difficult problem. This is mainly due to the fact that solutions of polynomial systems must be found and further processed, and the corresponding operations are computationally intensive. In the second part of the talk, I will outline how to improve the overall efficiency of such computations by combining techniques from different fields such as numerical analysis, computer algebra and algebraic geometry.
I will also report on recent algorithms that have been integrated in the computational geometry algorithms library (CGAL) and theoretical results which have been achieved during the last years.
Contact
jmueller@mpi-inf.mpg.de
2900
--email hidden
passcode not visible
logged in users only
Jennifer Müller, 10/27/2011 12:54
Jennifer Müller, 08/18/2011 09:48
Anna-Lisa Overhoff, 08/12/2011 10:14 -- Created document.
Jennifer Müller, 08/18/2011 09:48
Anna-Lisa Overhoff, 08/12/2011 10:14 -- Created document.