Most two-dimensional arrangements studied and computed to date are in the plane.
However, we often need two-dimensional arrangements on curved surfaces.
Consider for example, Gaussian maps of polytopes,
which in turn can be used to compute Minkowski sums of polytopes.
Here is a short sequence from an earlier movie that shows
how such Minkowski sums can be computed using six planar
arrangements embedded on the six facets of a cube.
While this technique proved to be efficient, it generated
additional vertices on the boundaries of the facets, and it
required identifying matching vertices on the boundaries of
abutting facets.
The six planar arrangements are induced by linear segments,
which can be handled with rational arithmetic.
Naturally, a rival technique that uses an
arrangement embedded on the sphere, eliminating the
additional boundary vertices, but still content with
rational arithmetic, has good chances to surpass its
competition.
Another example that demonstrates the usefulness of
arrangements on curved surfaces is the need to construct
and maintain arrangements induced by the intersections of
one surface with a collection of other surfaces.
We developed a general framework for computing arrangements
on two-dimensional parametric surfaces, which applies to a
variety of topologies including cylinder, torus, and
sphere.
It is based on the existing package that constructs
and maintains planar arrangements.
The domain is a rectangular two-dimensional parameter space with bottom,
top, left, and right boundaries.
An identification curve is a continuous curve, which is the mapping
of opposite closed boundaries of the domain.
A contraction point is a singular point, which is the mapping of
a whole boundary of the domain.
Code reuse is maximized by adapting the prevalent algorithms and
their implementations. For example, efficient point-location.
The generalized code handles features embedded on a modified
surface defined over a modified parameter space, where the
boundaries, identification curves, contraction points, and
points at infinity, are removed.
Specific code that handles features that approach or reach
the boundaries is added to yield a complete implementation.
As we sweep over the surface in order to construct a data
structure describing the arrangement of the curves, we have
to take into account the topology of the surface. Although
we removed the boundary of the parameter space, we now have
to account for the fact that several arcs pass through the
north pole which is a contraction point. When the sweep
line reaches the end of the parameter space, we have to
glue the arrangement features on the sweep line with their
counterparts that were discovered at the very beginning of
the sweep.
Most of the machinery developed in CGAL for planar
arrangements can now be used with arrangements on surfaces
provided that the user supplies the appropriate plug-ins
for the specific topology of a surface and the geometry of
the curves embedded on the surface. Here you see how two
arrangements are overlaid on the sphere.
The subdivision of the central sphere is the result of the
overlay of other spherical arrangements around it.
We can compute lower envelopes of
surfaces over the sphere which in turn we use to compute
Voronoi diagrams on the sphere. Here you can see an example,
where the point sites are rendered in red, and the diagram
is rendered in blue. The bisector of two point sites is a
geodesic arc.
Here you can see an example of a Power diagram on the sphere.
In this case, the sites are circles rendered in red.
The resulting diagrams are represented as arrangements and can
passed as input to consecutive operations supported by the arrangement
package. Here you can see the overlay of an arrangement induced by
the continents and the Voronoi diagram of the first 9 cities that hosted
the Symposium on Computational Geometry in this millenium.
More details can be found in the paper Sweeping and
Maintaining Two-Dimensional Arrangement on Surfaces: A
First Step, which was presented at ESA 2007 or in the following websites.