Arrangements of Geodesic Arcs on the Sphere

The overlay of: 1. an arrangement on the sphere  induced by the continents and some of the islands on earth rendered in blue, and 2.  the Voronoi diagram the cities that hosts the institutions that participate in the ACS (Algorithms for Complex Shapes) project rendered in red.

 Abstract

Recently, the Arrangement_2 package of CGAL, the Computational Geometry Algorithms Library, has been greatly extended to support arrangements of curves embedded on two-dimensional parametric surfaces. The general framework for sweeping a set of curves embedded on a two-dimensional parametric surface was introduced in[*]. In this project we concentrate on the specific algorithms and implementation details involved in the exact construction and maintenance of arrangements induced by arcs of great circles embedded on the sphere, also known as geodesic arcs, and on the exact computation of Voronoi diagrams on the sphere, the bisectors of which are geodesic arcs. This class of Voronoi diagrams includes the subclass of Voronoi diagrams of points and its generalization, power diagrams, also known as Laguerre Voronoi diagrams. The resulting diagrams are represented as arrangements, and can be passed as input to consecutive operations supported by the Arrangement_2 package and its derivatives. The implementation is complete in the sense that it handles degenerate input, and it produces exact results. An example that uses real world data is included.

Poster

Movie

Additional information

Links

• Efi Fogel, Ophir Setter and Dan Halperin
  Exact Implementation of Arrangements of Geodesic Arcs on the Sphere with Applications
  In Abstracts of 24th European Workshop on Computational Geometry (EWCG), pages 83-86, 2008 [pdf] [bibtex]
Efi Fogel, Ophir Setter and Dan Halperin
Arrangements of Geodesic arcs on the Sphere
In Proceedings of the 24th ACM Annual Symposium on Computational Geometry (SoCG), pages 218-219, 2008 [movie - additional information] [link] [bibtex]
• Eric Berberich, Efi Fogel, Dan Halperin, Kurt Mehlhorn, and Ron Wein
  Sweeping and Maintaining Two-Dimensional Arrangements on Surfaces: A First Step
  In Proceedings 15th Annual European Symposium on Algorithms (ESA), pages 645–656, 2007 [project site] [link] [bibtex]
• Eric Berberich, Efi Fogel, Dan Halperin, Kurt Melhorn, and Ron Wein,
  Arrangements on Parametric Surfaces I: General Framework and Infrastructure
  Mathematics in Computer Science, 4(1): 45-66, 2010 [link] [bibtex]
• Eric Berberich, Efi Fogel, Dan Halperin, Michael Kerber, and Ophir Setter,
  Arrangements on Parametric Surfaces II: Concretizations and Applications
  Mathematics in Computer Science, 4(1): 67-91, 2010 [link] [bibtex]

Contact

Efi Fogel
Dan Halperin