Campus Event Calendar
Event Entry
What and Who
Fast and Exact Geometric Analysis of Real Algebraic Plane Curves
Michael Kerber
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 25 July 2007
13:30
30 Minutes
E1 4
024
Saarbrücken
Abstract
An algorithm is presented for the geometric analysis of an algebraic curve f(x,y)=0 in the real affine plane. It computes a cylindrical algebraic decomposition (CAD) of the plane, augmented with adjacency information. The adjacency information describes the curve's topology by a topologically equivalent planar graph. The numerical data in the CAD gives an embedding of the graph.
The algorithm is designed to provide the exact result for all inputs but to perform only few symbolic operations for the sake of efficiency. In particular, the roots of f(\alpha,y) at a critical x-coordinate \alpha are found with adaptive-precision arithmetic in all cases, using a variant of the Bitstream Descartes method~(Eigenwillig et al., 2005). The algorithm may choose a generic coordinate system for parts of the analysis but provides its result in the original system.
The algorithm is implemented as C++ library AlciX in the EXACUS project. Running time comparisons with top by Gonzalez-Vega and Necula (2002), and with cad2d by Brown demonstrate its efficiency.
Contact
Michael Kerber
--email hidden
passcode not visible
logged in users only
Michael Kerber, 07/19/2007 09:20 -- Created document.