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 35 articles )

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

1 2 next

  1. Attali, Dominique; Nguyen, Tuong-Bach; Sivignon, Isabelle: ((\delta,\varepsilon))-ball approximation of a shape: definition and complexity (2019)
  2. Baram, Alon; Fogel, Efi; Halperin, Dan; Hemmer, Michael; Morr, Sebastian: Exact Minkowski sums of polygons with holes (2018)
  3. Baram, Alon; Fogel, Efi; Halperin, Dan; Hemmer, Michael; Morr, Sebastian: Exact Minkowski sums of polygons with holes (2015)
  4. Barki, Hichem; Guennebaud, Gaël; Foufou, Sebti: Exact, robust, and efficient regularized Booleans on general 3D meshes (2015)
  5. Sivignon, Isabelle: Fast recognition of a digital straight line subsegment: two algorithms of logarithmic time complexity (2015)
  6. Hakula, Harri: (hp)-boundary layer mesh sequences with applications to shell problems (2014)
  7. Kunigami, Guilherme; de Rezende, Pedro J.; de Souza, Cid C.; Yunes, Tallys: Optimizing the layout of proportional symbol maps: polyhedra and computation (2014)
  8. Berberich, Eric; Emeliyanenko, Pavel; Kobel, Alexander; Sagraloff, Michael: Exact symbolic-numeric computation of planar algebraic curves (2013)
  9. Zhang, Qinghai: On a family of unsplit advection algorithms for volume-of-fluid methods (2013)
  10. Fogel, Efi; Halperin, Dan; Wein, Ron: CGAL Arrangements and their applications. A step-by-step guide (2012)
  11. Hemmer, Michael; Kleinbort, Michal; Halperin, Dan: Improved implementation of point location in general two-dimensional subdivisions (2012)
  12. Kröller, Alexander; Baumgartner, Tobias; Fekete, Sándor P.; Schmidt, Christiane: Exact solutions and bounds for general art gallery problems (2012)
  13. Berberich, Eric; Fogel, Efi; Halperin, Dan; Kerber, Michael; Setter, Ophir: Arrangements on parametric surfaces. II: Concretizations and applications (2010)
  14. Berberich, Eric; Fogel, Efi; Halperin, Dan; Mehlhorn, Kurt; Wein, Ron: Arrangements on parametric surfaces. I: General framework and infrastructure (2010)
  15. Berberich, Eric; Kerber, Michael; Sagraloff, Michael: An efficient algorithm for the stratification and triangulation of an algebraic surface (2010)
  16. Fogel, Efi; Halperin, Dan: Polyhedral assembly partitioning with infinite translations or the importance of being exact (2010)
  17. Kels, Shay; Dyn, Nira; Lipovetsky, Evgeny: Computation of the metric average of 2D sets with piecewise linear boundaries (2010)
  18. Setter, Ophir; Sharir, Micha; Halperin, Dan: Constructing two-dimensional Voronoi diagrams via divide-and-conquer of envelopes in space (2010)
  19. van den Berg, Jur; Stilman, Mike; Kuffner, James; Lin, Ming; Manocha, Dinesh: Path planning among movable obstacles: A probabilistically complete approach (2010)
  20. Berberich, Eric; Sagraloff, Michael: A generic and flexible framework for the geometrical and topological analysis of (algebraic) surfaces (2009)

1 2 next