An Exact, Complete and Efficient Implementation for Computing Planar Maps of Quadric Intersection Curves

We present the first exact, complete and efficient implementation that computes for a given set $P=\{p_1,\dots,p_n\}$ of quadric surfaces the planar map induced by all intersection curves $p_1\cap p_i$, $2\leq i\leq n$, running on the surface of $p_1$. 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~[20] and~[9]. Our implementation is {\em 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 {\em exact} in that it always computes the mathematical correct result. It is {\em efficient} measured in running times