D. Russel, M. I. Karavelas and L. J. Guibas. A package for Exact Kinetic Data Structures and Sweepline Algorithms. Computational Geometry: Theory and Applications, Special Issue on CGAL, 38(1-2):111-127, September 2007.

Abstract:

In this paper we present a package for implementing exact kinetic data structures built on objects which move along polynomial trajectories. We discuss how the package design was influenced by various considerations, including extensibility, support for multiple kinetic data structures, access to existing data structures and algorithms in CGAL, as well as debugging. Due to the similarity between the operations involved, the software can also be used to compute arrangements of polynomial objects using a sweepline approach. The package consists of three main parts, the kinetic data structure framework support code, an algebraic kernel which implements the set of algebraic operations required for kinetic data structure processing, and kinetic data structures for Delaunay triangulations in one and two dimensions, and Delaunay and regular triangulations in three dimensions. The models provided for the algebraic kernel support both exact operations and inexact approximations with heuristics to improve numerical stability.

Bibtex: 

@article{rkg-pekdssa-07, 
, author = "Daniel Russel and Menelaos Karavelas and Leonidas Guibas
, journal = "Computational Geometry: Theory and Applications"
, title = "A Package for Exact Kinetic Data Structures and Sweepline Algorithms"
, year = 2007
, volume = 38
}