Search
Close this search box.

Arrangements of Geodesic Arcs on the Sphere

Abstract

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

Recently, the 2D Arrangement 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 2D Arrangement 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

poster

 

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 (EuroCG), 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 FogelDan 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), Volume 4698 of LNCS, 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]

Contacts

Efi Fogel
Dan Halperin
@inproceedings{fsh-eiaga-08,
  title        = {Exact Implementation of Arrangements of Geodesic Arcs on the Sphere with Applications},
  author       = {Efi Fogel and Ophir Setter and Dan Halperin},
  booktitle    = {Proceedings of the 24th European Workshop on Computational Geometry ({EuroCG})},
  pages        = {83--86},
  year         = {2008},
  site         = {Nancy, France}
}
@inproceedings{fsh-agas-08,
  title        = {Arrangements of Geodesic Arcs on the Sphere},
  author       = {Efi Fogel and Ophir Setter and Dan Halperin},
  booktitle    = {Proceedings of the 24th annual symposium on Computational geometry ({SoCG})},
  pages        = {218--219},
  year         = {2008},
  site         = {College Park, MD, USE},
  doi          = {10.1145/1377676.137771}
}
@inproceedings{bfhmw-scmtd-07,
  author       = {Eric Berberich and Efi Fogel and Dan Halperin and Kurt Melhorn and and Ron Wein},
  title        = {Sweeping and Maintaining Two-Dimensional Arrangements on Surfaces: A First Step},
  year         = {2007},
  pages        = {645--656},
  booktitle    = {Proceedings of the 15th Annual European Symposium on Algorithms ({ESA})},
  series       = {Lecture Notes in Computer Science ({LNCS})},
  volume       = {4698},
  editor       = {Lars Arge and Michael Hoffmann and Emo Welzl},
  publisher    = {Springer},
  address      = {Eilat, Israel}
  doi          = {10.1007/978-3-540-75520-3_57}
}
@article{bfhks-scmtd-ii-07,
  author      = {Eric Berberich and Efi Fogel and Dan Halperin and Michael Kerber and Ophir Setter},
  title       = {Arrangements on Parametric Surfaces {II}: Concretizations and Applications},
  journal     = {Mathematics in Computer Science},
  publisher   = {Birkh\"{a}user Basel},
  pages       = {67--91},
  volume      = {4},
  issue       = {1},
  doi         = {10.1007/s11786-010-0043-4},
  year        = {2010}
}
@article{bfhmw-scmtd-i-07,
  author      = {Eric Berberich and Efi Fogel and Dan Halperin and Kurt Melhorn and and Ron Wein},
  title       = {Arrangements on Parametric Surfaces {I}: General Framework and Infrastructure},
  journal     = {Mathematics in Computer Science},
  publisher   = {Birkh\"{a}user Basel},
  pages       = {67--91},
  volume      = {4},
  issue       = {1},
  doi         = {10.1007/s11786-010-0043-4},
  year        = {2010}
}

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
720×576, DivX, ~30M
720×576, XviD, ~125M
360×288, DivX, ~27M
360×288, XviD, ~31M

English subtitles (subrip)
Hebrew subtitles (subrip)

References

  1. F. Aurenhammer and R. Klein
    Voronoi diagrams
    In J. Sack and G. Urrutia, editors, Handbook Computational Geometry, chapter 5, pages 201-290, Elsevier, 2000
  2. Eric Berberich, Efi Fogel, Dan Halperin, K. Melhorn, and R. Wein
    Sweeping and maintaining two-dimensional arrangements on surfaces: A first step
    In Proceedings 15th Annual European Symposium on Algorithms, pages 645-656, 2007
  3. Eric Berberich and M. Kerber
    Exact arrangements on tori and Dupin cyclides
    In Proceedings ACM Solid Physics Modeling Symposium, 2008
  4. H. Edelsbrunner and R. Seidel
    Voronoi diagrams and arrangements
    Discrete Computational Geometry, 1:25-44, 1986
  5. Dan Halperin, O. Setter, and M. Sharir
    Constructing two-dimensional Voronoi diagrams via divide-and-conquer of envelopes in space
    Manuscript, 2008
  6. M. Meyerovitch
    Robust, generic and efficient construction of envelopes of surfaces in three-dimensional space
    In Proceedings 14th Annual European Symposium on Algorithms, pages 792-803, 2006. [project page]
  7. K. Sugihara
    Laguerre Voronoi diagram on the sphere
    Journal for Geom. Graphics, 6(1):69-81, 2002
  8. R. Wein, Efi Fogel, B. Zukerman, and Dan Halperin
    Advanced programming techniques applied to CGAL arrangement package
    Computational Geometry Theory & Applications, 38(1-2):37-63, 2007; special issue on CGAL

Yair Oz - Webcreator

Contact

Skip to content