Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF D1 Publications :: Thesis :: Kerber, Michael

MPI-INF D1 Publications
Show all entries of:this year (2020)last year (2019)two years ago (2018)Open in Notes
Action:login to update

Thesis - Master's thesis | @MastersThesis | Masterarbeit

Author(s)*:Kerber, Michael
BibTeX citekey*:Kerber2006

Title, School
Title*:Analysis of Real Algebraic Plane Curves
School:Universität des Saarlandes
Type of Thesis*:Master's thesis

Note, Abstract, Copyright
LaTeX Abstract:This work describes a new method to compute geometric properties of a real algebraic plane curve of arbitrary degree. These properties contain the topology of the curve as well as the location of singular points and vertical asymptotes. The algorithm is based on the Bitstream Descartes method (Eigenwillig et al.: ``A Descartes Algorithm for Polynomials with Bit-Stream Coefficients'', LNCS~3718), which computes exact information about the real roots of a polynomial from approximate coefficients. For symbolic calculations with algebraic numbers, especially for counting distinct real roots, it uses Sturm-Habicht sequences (Gonzalez-Vega et al.: ``Sturm-Habicht Sequences \ldots'', in: Caviness, Johnson(eds.): {\it Quantifier Elimination\ldots}, Springer, 1998), which are related to polynomial remainder sequences. Our work explains how to combine these methods to reduce the amount of symbolic calculations without losing exactness.\par

The geometry of the curve is computed with respect to the predetermined coordinate system. The algorithm changes coordinates in some situations to bring the curve into a generic position, but a new technique transports the computed information back into the original system efficiently. The conditions for a generic position of the curve are less restrictive than in other approaches and can be checked more efficiently during the analysis.\par
The algorithm has been implemented as part of the software library EXACUS. This work presents comprehensive experimental results. They show that the new approach consistently outperforms the method by Seidel and Wolpert (``On the Exact Computation \ldots'', SCG 2005, 107--115) and the frequently cited algorithm of Gonzalez-Vega and Necula (``Efficient Topology Determination \ldots'', {\it Comp.\ Aided Design} {\bf 19} (2002) 719--743). We therefore claim that our algorithm reflects the state-of-the-art in the resultant-based analysis of algebraic curves.

Keywords:Computational Geometry

Referees, Status, Dates
1. Referee:Kurt Mehlhorn
2. Referee:Nicola Wolpert
Supervisor:Arno Eigenwillig, Kurt Mehlhorn, Nicola Wolpert
Date Kolloquium:- - -

MPG Unit:Max-Planck-Institut für Informatik
MPG Subunit:Algorithms and Complexity Group
MPG Subsubunit:Computational geometry
Audience:experts only
Appearance:MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:
AUTHOR = {Kerber, Michael},
TITLE = {Analysis of Real Algebraic Plane Curves},
SCHOOL = {Universit{\"a}t des Saarlandes},
YEAR = {2006},
TYPE = {Master's thesis}
MONTH = {September},

Entry last modified by Michael Kerber, 02/27/2007
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Michael Kerber
11/22/2006 01:59:52 PM

Michael Kerber
Michael Kerber

Edit Date
02/27/2007 03:07:09 PM
22.11.2006 13:59:53