Arrangements of Geodesic Arcs on the Sphere - Additional Information
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.
- F. Aurenhammer and R. Klein. Voronoi diagrams. In J. Sack and G. Urrutia, editors, Handb. Comput. Geom., chapter 5, pages 201-290. Elsevier, 2000.
- 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.
- E. Berberich and M. Kerber. Exact arrangements on tori and Dupin cyclides. In Proc. ACM Solid Phys. Model. Symp. 2008. To appear.
- H. Edelsbrunner and R. Seidel. Voronoi diagrams and arrangements. Disc. Comput. Geom., 1:25-44, 1986.
- D. Halperin, O. Setter, and M. Sharir. Constructing two-dimensional Voronoi diagrams via divide-and-conquer of envelopes in space, 2008. Manuscript.
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]
- K. Sugihara. Laguerre Voronoi diagram on the sphere. J. for Geom. Graphics, 6(1):69-81, 2002.
- 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.
* 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.