An exact and efficient approach for computing a cell in an arrangement of quadrics

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 tagential intersections and singular points. By introducing an additional curve, which we call the 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.

In dieser Doktorarbeit stellen wir einen Ansatz vor, mit dessen Hilfe eine Zelle in einem Arrangement von quadratischen Flächen exakt und effizient berechnet werden kann. Alle Berechnungen basieren auf exakten algebraischen Methoden und führen selbst in degenerierten Fällen zu mathematisch korrekten Ergebnissen. Durch Projektion kann das räumliche Problem darauf reduziert werden, planare Arrangements von Kurven zu bestimmen. Es gelingt uns, alle Ereignispunkte dieser planaren Arrangements einschliesslich der tangentialen Schnitte und singulären Punkte zu lokalisieren. Die nicht singulären tangentialen Schnitte bestimmen wir, indem wir eine zusätzliche Kurve, die wir Jacobi Kurve nennen, betrachten. Durch eine Verallgemeinerung der Jacobi Kurve sind wir in der Lage, in beliebigen planaren Arrangements nicht-singuläre tangentiale Schnitte zu bestimmen. Wir zeigen, dass die Koordinaten der singulären Punkte in unseren speziellen, durch Projektion entstandenen, planaren Arrangements Nullstellen von quadratischen Polynomen sind. Die Koeffizienten dieser Polynome sind in den meisten Fällen rational und benötigen maximal eine einzelne Quadratwurzel. Eine prototypische Implementierung zeigt, dass unser Ansatz in der Praxis zu einem guten Laufzeitverhalten führt.