Personal tools
You are here: Home Projects Internal Projects Arrangements of Geodesic Arcs on the Sphere Movie Arrangements of Geodesic Arcs on the Sphere - Additional Information
« March 2017 »
Log in

Forgot your password?

Arrangements of Geodesic Arcs on the Sphere - Additional Information

Movie page


This movie illustrates exact construction and maintenance of arrangements induced by arcs of great circles embedded on the sphere, also known as geodesic arcs, and 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 of Cgal and its derivatives. The implementation handles well degenerate input and produces exact results.


Article PDF

The Movie

720x576, DivX, ~30M
720x576, XviD, ~125M
360x288, DivX, ~27M
360x288, XviD, ~31M


English subtitles (subrip)
Hebrew subtitles (subrip)


  1. F. Aurenhammer and R. Klein. Voronoi diagrams. In J. Sack and G. Urrutia, editors, Handb. Comput. Geom., chapter 5, pages 201-290. Elsevier, 2000.
  2. E. Berberich, E. Fogel, D. Halperin, K. Melhorn, and R. Wein. Sweeping and maintaining two-dimensional arrangements on surfaces: A first step. In Proc. 15th Annu. Eur. Symp. Alg., pages 645-656, 2007.
  3. E. Berberich and M. Kerber. Exact arrangements on tori and Dupin cyclides. In Proc. ACM Solid Phys. Model. Symp. 2008. To appear.
  4. H. Edelsbrunner and R. Seidel. Voronoi diagrams and arrangements. Disc. Comput. Geom., 1:25-44, 1986.
  5. D. Halperin, O. Setter, and M. Sharir. Constructing two-dimensional Voronoi diagrams via divide-and-conquer of envelopes in space, 2008. Manuscript.
  6. M. Meyerovitch. Robust, generic and efficient construction of envelopes of surfaces in three-dimensional space. In Proc. 14th Annu. Eur. Symp. Alg., pages 792-803, 2006. [project page]

  7. K. Sugihara. Laguerre Voronoi diagram on the sphere. J. for Geom. Graphics, 6(1):69-81, 2002.
  8. R. Wein, E. Fogel, B. Zukerman, and D. Halperin. Advanced programming techniques applied to Cgal's arrangement package. Comput. Geom. Theory Appl., 38(1-2):37-63, 2007. Special issue on Cgal.


Efi Fogel
Ophir Setter
Dan Halperin
Document Actions


* This work has been supported in part by the IST Programme of the EU as Shared-cost RTD (FET Open) Project under Contract No IST006413 (ACS - Algorithms for Complex Shapes), by the Israel Science Foundation (grant no. 236/06), and by the Hermann Minkowski- Minerva Center for Geometry at Tel Aviv University.

Document Actions