Sweeping and Maintaining Two-Dimensional Arrangements on Surfaces: A First Step

摘要

We introduce a general framework for sweeping a set of curves embedded on a two-dimensional parametric surface. We can handle planes, cylinders, spheres, tori, and surfaces homeomorphic to them. A major goal of our work is to maximize code reuse by generalizing the prevalent sweep-line paradigm and its implementation so that it can be employed on a large class of surfaces and curves embedded on them. We have realized our approach as a prototypical CGAL package. We present experimental results for two concrete adaptations of the framework: (ⅰ) arrangements of arcs of great circles embedded on a sphere, and (ⅱ) arrangements of intersection curves between quadric surfaces embedded on a quadric.