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
« August 2017 »
August
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
2728293031
Log in


Forgot your password?
 

Arrangements of Geodesic Arcs on the Sphere - Additional Information

Movie page

Abstract

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.

Description

Article PDF

The Movie

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

 

English subtitles (subrip)
Hebrew subtitles (subrip)

References

  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.

Contact

Efi Fogel
http://www.cs.tau.ac.il/~eitanyaf eitan.yaffe@gmail.com
Ophir Setter
http://www.cs.tau.ac.il/~eitanyaf eitan.yaffe@gmail.com
Dan Halperin http://www.cs.tau.ac.il/~danha danha@post.tau.ac.il
 
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