MPI-INF Logo
Publications

Thesis (Server    domino.mpi-inf.mpg.de)

Thesis

Doctoral dissertation | @PhdThesis{WolpertDiss2002, ... | Doktorarbeit

Wolpert, Nicola

An Exact and Efficient Approach for Computing a Cell in an Arrangement of Quadrics

Universität des Saarlandes, October, 2002

In this thesis, we present an approach for the exact and efficient
computation of a cell in an arrangement of quadric surfaces. All
calculations are based on exact rational algebraic methods and provide
the correct mathematical results in all, even degenerate, cases. By
projection, the spatial problem can be reduced to the one of computing
planar arrangements of algebraic curves. We succeed in locating all
event points in these arrangements, including tangential intersections
and singular points. By introducing an additional curve, which we call
the {\em Jacobi curve}, we are able to find non-singular tangential
intersections. By a generalization of the Jacobi curve we are able to
determine non-singular tangential intersections in arbitrary planar
arrangements. We show that the coordinates of the singular points in
our special projected planar arrangements are roots of quadratic
polynomials. The coefficients of these polynomials are usually
rational and contain at most a single square root. A prototypical
implementation indicates that our approach leads to good performance in
practice.

Public
Download File(s):
Professor Dr. Raimund Seidel
Professor Dr. Kurt Mehlhorn
Professor Dr. Raimund Seidel
Completed
31
October
2002
Professor Dr. Reinhard Wilhelm
Max-Planck-Institut für Informatik
Algorithms and Complexity Group
Expert
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat


BibTeX Entry:
@PHDTHESIS{WolpertDiss2002,
AUTHOR = {Wolpert, Nicola},
TITLE = {An Exact and Efficient Approach for Computing a Cell in an Arrangement of Quadrics},
SCHOOL = {Universit{\"a}t des Saarlandes},
YEAR = {2002},
TYPE = {Doctoral dissertation}
MONTH = {October},
}





Entry last modified by Christine Kiesel, 03/02/2010
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)

Editor(s)
Nicola Wolpert
Created
01/15/2003 05:38:58 PM
Revision
1.
0.


Editor
Christine Kiesel
Nicola Wolpert


Edit Date
08.09.2003 18:47:04
15/01/2003 17:38:58