Refereed Conference Paper

An Exact, Complete and Efficient Implementation for Computing Planar Maps of Quadric Intersection Curves. Eric Berberich, Michael Hemmer, Lutz Kettner, Elmar Schömer, and Nicola Wolpert. In: Proc. of the 21st ACM Symp. on Computational Geometry, Pisa Italy, pp. ..., June 2005.

Abstract

We present the first exact, complete and efficient implementation that computes for a given set P={p₁,...,p_n} of quadric surfaces the planar map induced by all intersection curves p₁ p_i, 2 <= i <= n, running on the surface of p₁. The vertices in this graph are the singular and x-extreme points of the curves as well as all intersection points of pairs of curves. Two vertices are connected by an edge if the underlying points are connected by a branch of one of the curves. Our work is based on and extends ideas developed in [Schömer&Wolpert 2004] and [Eigenwillig et.al. 2004].

Our implementation is complete in the sense that it can handle all kind of inputs including all degenerate ones where intersection curves have singularities or pairs of curves intersect with high multiplicity. It is exact in that it always computes the mathematical correct result. It is efficient measured in running times.