Exact computation of the adjacency graph of an arrangement of quadrics [Elektronische Ressource] / vorgelegt von Michael Hemmer

Exact Computation of the Adjacency Graph ofan Arrangement of QuadricsDissertationzur Erlangung des Grades”Doktor der Naturwissenschaften”am Fachbereich Physik, Mathematik und Informatikder Johannes Gutenberg-Universit at in Mainz,vorgelegt vonMichael Hemmergeboren in Puttlingen.Mainz, den 18. September 2007AbstractWe present a complete, exact and e cient algorithm to compute the adjacency graphof an arrangement of quadrics, i.e. surfaces of algebraic degree 2. This is a ma-jor step towards the computation of the full 3D arrangement. We enhanced animplementation [58] for an exact parameterization of the intersection curves of twoquadrics [23, 24, 25], such that we can compute the exact parameter value for intersec-tionpointsandfromthattheadjacencygraphofthearrangement. Ourimplementationis complete in the sense that it can handle all kinds of inputs including all degenerateones, i.e. singularities or tangential intersection points. It is exact in that it alwayscomputes the mathematically correct result. It is e cient measured in running times,i.e. it compares favorably to the only previously implemented approach.Our approach has been implemented within the Exacus [6] project. The centralgoal of Exacus is the development of a demonstrator of a reliable and e cient CADgeometrykernel. Althoughwecallourlibrarydesignprototypical,wespentnonethelessa great e ort on completeness, exactness, e ciency, documentation and reusability.