# Fast and Exact Geometric Analysis of Real Algebraic Plane Curves

Tuesday, May 29, 2007 - 2:00pm - 2:30pm

EE/CS 3-180

Nicola Wolpert (Stuttgart University of Applied Sciences)

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 (a,y) at a critical x-coordinate a 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 has been 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.

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 (a,y) at a critical x-coordinate a 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 has been 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.

MSC Code:

14Pxx

Keywords: