2D Arrangement

This package can be used to construct, maintain, alter, and display arrangements in the plane. Once an arrangement is constructed, the package can be used to obtain results of various queries on the arrangement, such as point location. The package also includes generic implementations of two algorithmic frameworks, that are, computing the zone of an arrangement, and line-sweeping the plane, the arrangements is embedded on. These frameworks are used in turn in the implementations of other operations on arrangements. Computing the overlay of two arrangements, for example, is based on the sweep-line framework. Arrangements and arrangement components can also be extended to store additional data. An important extension stores the construction history of the arrangement, such that it is possible to obtain the originating curve of an arrangement subcurve.

References in zbMATH (referenced in 28 articles )

Showing results 1 to 20 of 28.
Sorted by year (citations)

1 2 next

  1. Sivignon, Isabelle: Fast recognition of a digital straight line subsegment: two algorithms of logarithmic time complexity (2015)
  2. Hakula, Harri: $hp$-boundary layer mesh sequences with applications to shell problems (2014)
  3. Berberich, Eric; Emeliyanenko, Pavel; Kobel, Alexander; Sagraloff, Michael: Exact symbolic-numeric computation of planar algebraic curves (2013)
  4. Zhang, Qinghai: On a family of unsplit advection algorithms for volume-of-fluid methods (2013)
  5. Fogel, Efi; Halperin, Dan; Wein, Ron: CGAL Arrangements and their applications. A step-by-step guide (2012)
  6. Hemmer, Michael; Kleinbort, Michal; Halperin, Dan: Improved implementation of point location in general two-dimensional subdivisions (2012)
  7. Kröller, Alexander; Baumgartner, Tobias; Fekete, Sándor P.; Schmidt, Christiane: Exact solutions and bounds for general art gallery problems (2012)
  8. Berberich, Eric; Fogel, Efi; Halperin, Dan; Kerber, Michael; Setter, Ophir: Arrangements on parametric surfaces. II: Concretizations and applications (2010)
  9. Berberich, Eric; Fogel, Efi; Halperin, Dan; Mehlhorn, Kurt; Wein, Ron: Arrangements on parametric surfaces. I: General framework and infrastructure (2010)
  10. Berberich, Eric; Kerber, Michael; Sagraloff, Michael: An efficient algorithm for the stratification and triangulation of an algebraic surface (2010)
  11. Fogel, Efi; Halperin, Dan: Polyhedral assembly partitioning with infinite translations or the importance of being exact (2010)
  12. Setter, Ophir; Sharir, Micha; Halperin, Dan: Constructing two-dimensional Voronoi diagrams via divide-and-conquer of envelopes in space (2010)
  13. van den Berg, Jur; Stilman, Mike; Kuffner, James; Lin, Ming; Manocha, Dinesh: Path planning among movable obstacles: A probabilistically complete approach (2010)
  14. Berberich, Eric; Sagraloff, Michael: A generic and flexible framework for the geometrical and topological analysis of (algebraic) surfaces (2009)
  15. Cazals, Frédéric; Loriot, Sébastien: Computing the arrangement of circles on a sphere, with applications in structural biology (2009)
  16. de Castro, Pedro M.M.; Cazals, Frédéric; Loriot, Sébastien; Teillaud, Monique: Design of the CGAL 3D spherical kernel and application to arrangements of circles on a sphere (2009)
  17. Hanniel, Iddo; Elber, Gershon: Computing the Voronoi cells of planes, spheres and cylinders in $\bbfR^3$ (2009)
  18. Haran, Idit; Halperin, Dan: An experimental study of point location in planar arrangements in CGAL (2009)
  19. Alon, Noga; Halperin, Dan; Nechushtan, Oren; Sharir, Micha: The complexity of the outer face in arrangements of random segments (2008)
  20. Berberich, Eric; Kerber, Michael; Sagraloff, Michael: Exact geometric-topological analysis of algebraic surfaces (2008)

1 2 next