Exact arrangements on tori and Dupin cyclides

Abstract

An algorithm and implementation is presented to compute the exact arrangement\ninduced by arbitrary algebraic surfaces on a parametrized ring Dupin cyclide.\nThe family of Dupin cyclides contains as a special case the torus.\nThe intersection of an algebraic surface of degree $n$ with a reference\ncyclide is represented as a real algebraic curve of bi-degree $(2n,2n)$\nin the two-dimensional parameter space of the cyclide.\nWe use Eigenwillig and Kerber:\n``Exact and Efficient 2D-Arrangements of Arbitrary Algebraic Curves'', \nSODA~2008, to compute a planar arrangement of such curves\nand extend their approach to obtain more asymptotic information about curves \napproaching the boundary of the cyclide's parameter space. \nWith that, we can base our implementation on the general software framework\nby Berberich~et.~al.: ``Sweeping and Maintaining Two-Dimensional \nArrangements on Surfaces: A First Step'', ESA~2007.\nOur contribution provides the demanded techniques to model the special\ngeometry of surfaces intersecting a cyclide\nand the special topology of the reference surface of genus one.\nThe contained implementation is complete and does not assume generic position. \nOur experiments show that the combinatorial overhead of the framework\ndoes not harm the efficiency of the method. Our experiments show that the\noverall performance is strongly coupled to the efficiency of the\nimplementation for arrangements of algebraic plane curves.