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

Wolpert, Nicola

doi:10.22028/D291-25753

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Thesis

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

MPS-Authors

/persons/resource/persons45758

Wolpert, Nicola
Algorithms and Complexity, MPI for Informatics, Max Planck Society;
International Max Planck Research School, MPI for Informatics, Max Planck Society;

External Resource

http://scidok.sulb.uni-saarland.de/volltexte/2004/248/
(Any fulltext)

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Wolpert, N. (2002). An Exact and Efficient Approach for Computing a Cell in an Arrangement of Quadrics. PhD Thesis, Universität des Saarlandes, Saarbrücken. doi:10.22028/D291-25753.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2EFC-A

Abstract

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.