Arrangements on Parametric Surfaces II: Concretizations and Applications |
| |
Authors: | Eric Berberich Efi Fogel Dan Halperin Michael Kerber Ophir Setter |
| |
Institution: | (2) School of Computer Science, Tel-Aviv University, Tel Aviv, Israel |
| |
Abstract: | We describe the algorithms and implementation details involved in the concretizations of a generic framework that enables
exact construction, maintenance, and manipulation of arrangements embedded on certain two-dimensional orientable parametric
surfaces in three-dimensional space. The fundamentals of the framework are described in a companion paper. Our work covers
arrangements embedded on elliptic quadrics and cyclides induced by intersections with other algebraic surfaces, and a specialized
case of arrangements induced by arcs of great circles embedded on the sphere. We also demonstrate how such arrangements can
be used to accomplish various geometric tasks efficiently, such as computing the Minkowski sums of polytopes, the envelope
of surfaces, and Voronoi diagrams embedded on parametric surfaces. We do not assume general position. Namely, we handle degenerate
input, and produce exact results in all cases. Our implementation is realized using Cgal and, in particular, the package that provides the underlying framework. We have conducted experiments on various data sets,
and documented the practical efficiency of our approach. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|