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

MPI-INF D1 Publications :: Thesis :: Hemmer, 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 - Doctoral dissertation | @PhdThesis | Doktorarbeit

Author(s)*:Hemmer, Michael
BibTeX citekey*:Hemmer2008

Title, School
Title*:Exact Computation of the Adjacency Graph of an Arrangement of Quadrics
School:Johannes Gutenberg-Universität Mainz
Type of Thesis*:Doctoral dissertation

Publishers Name:Johannes Gutenberg-Universität Mainz
Publishers Address:Saarstr. 21, D 55122 Mainz

Note, Abstract, Copyright
LaTeX Abstract:We present a complete, exact and efficient algorithm to compute the adjacency graph of an arrangement of quadrics, i.e. surfaces of algebraic degree 2. This is a major step towards the computation of the full 3D arrangement. We enhanced an implementation for an exact parameterization of the intersection curves of two quadrics, such that we can compute the exact parameter value for intersection points and from that the adjacency graph of the arrangement. Our implementation is complete in the sense that it can handle all kinds of inputs including all degenerate ones, i.e. singularities or tangential intersection points. It is exact in that it always computes the mathematically correct result. It is efficient measured in running times, i.e. it compares favorably to the only previously implemented approach. Our approach has been implemented within the EXACUS project. The central goal of Exacus is the development of a demonstrator of a reliable and efficient CAD geometry kernel. Although we call our library design prototypical, we spent nonetheless a great effort on completeness, exactness, efficiency, documentation and reusability. Beside its primary contribution, the algorithm presented in this work had an essential impact on fundamental parts of EXACUS due to its specific requirements. This work has in particular contributed to the generic number type support and the modular methods used within Exacus. In the context of our ongoing integration of EXACUS into CGAL these parts have been successfully advanced into mature CGAL packages.
Keywords:Exact Geometric Computing, Arrangements, Quadrics, Generic Programming
HyperLinks / References / URLs:;

Download Access Level:Public
Download File(s):View attachments here:

Referees, Status, Dates
1. Referee:Kurt Mehlhorn
2. Referee:Dan Halperin
Supervisor:Elmar Schömer
First Lecture Title:-
Location of Lecture:-
Date Kolloquium:29 May 2008
Chair Kolloquium:Duco van Straten

MPG Unit:Max-Planck-Institut für Informatik
MPG Subunit:Algorithms and Complexity Group
External Affiliations:Johannes Gutenberg-Universität Mainz
Research Context:Exact Geometric Computing; Arrangements; Quadrics; Generic Programming; CGAL
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 = {Hemmer, Michael},
TITLE = {Exact Computation of the Adjacency Graph of an Arrangement of Quadrics},
PUBLISHER = {Johannes Gutenberg-Universität Mainz},
SCHOOL = {Johannes Gutenberg-Universit{\"a}t Mainz},
YEAR = {2008},
TYPE = {Doctoral dissertation}
ADDRESS = {Saarstr. 21, D 55122 Mainz},
MONTH = {May},

Entry last modified by Michael Hemmer, 03/27/2009
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 Hemmer
01/26/2009 03:05:29 PM

Michael Hemmer
Michael Hemmer
Michael Hemmer

Edit Dates
03/27/2009 10:44:57 AM
01/26/2009 03:09:45 PM
01/26/2009 03:05:29 PM