Implementing Four-Dimensional Triangulations in CGAL

This thesis presents the implementation of a four-dimensional triangulation package. Computation of both basic triangulations of point sets and regular triangulations of weighted point sets using an incremental insertion algorithm is presented. The regular triangulation is the dual of the power diagram, which is the Voronoi diagram of weighted points under the power distance. The implementation follows the Computational Geometry Algorithms Library (CGAL), and will be contributed. A key part of the package lies with the data structure, which allows the user to easily traverse the constructed triangulations using circulators, enumerators, and iterators. Additionally, the geometric predicates are generalized from their lower-dimensional counterparts. Arithmetic filtering is used to keep the predicates exact, yet efficient. The result is a triangulation package that is easy to use, efficient, and robust.