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.


We present the first exact, complete and efficient implementation that computes for a given set P={p1,...,pn} of quadric surfaces the planar map induced by all intersection curves p1 pi, 2 <= i <= n, running on the surface of p1. 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 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.

[PDF] © ACM 2005.
[PostScript] © ACM 2005.
[EXACUS Home Page]

Lutz Kettner (<surname> Last modified on Friday, 15-Jul-2005 18:55:31 MEST.