Transforming a geometric algorithm into an effective computer program is a difficult task. This transformation is particularly made hard by the basic assumptions of most theoretical geometric algorithms concerning complexity measures and (more crucially) the handling of robustness issues, namely issues related to arithmetic precision and degenerate input. The paper starts with a discussion of the gap between the theory and practice of geometric algorithms, together with a brief review of existing solutions to some of the problems that this dichotomy brings about.
We then turn to an overview of the CGAL project and library. The CGAL project is a joint effort by a number of research groups in Europe and Israel to produce a robust software library of geometric algorithms and data structures. The library is now available for use with significant functionality. We describe the main goals and results of the project.
The central part of the paper is devoted to arrangements (i.e., space subdivisions induced by geometric objects) and motion planning. We concentrate on the maps and arrangements part of the CGAL library. Then we describe two packages developed on top of CGAL for constructing robust geometric primitives for motion algorithms.
Abrams, S., and Allen, P.1995. Swept volumes and their use in viewpoint computation in robot work-cells. In Proc. IEEE Intl. Symposium on Assembly and Task Planning, pp. 188- 193.
2.
Agarwal, P., and Sharir, M.1999. Arrangements. In Handbook of Computational Geometry, eds. J.-R. Sack and J. Urrutia, 49-119. North-Holland, Amsterdam: Elsevier Science Publishers B.V.
3.
Agarwal, P.K., Flato, E., and Halperin, D.2002. Polygon decomposition for efficient construction of Minkowski sums. Computational Geom. Theory Appl. 21:39-61.
4.
Agarwal, P.K., Katz, M., and Sharir, M.1995. Computing depth orders for fat objects and related problems . Computational Geom. Theory Appl. 5:187-206.
5.
Aharoni, Y., Halperin, D., Hanniel, I., Har-Peled, S., and Linhart, C.1999. On-line zone construction in arrangements of lines in the plane. In Proc. of the 3rd Workshop of Algorithm Engineering, vol. 1668 of Lecture Notes Computer Sci., 139-153. Springer-Verlag. Full version: www.cs.tau.ac.il/″danha/papers/onlinezone.ps.gz .
6.
Amenta, N.1997. Computational geometry software. In Handbook of Discrete and Computational Geometry, eds. J. E. Goodman and J. O'Rourke, chap. 52, 951-960. Boca Raton, FL: CRC Press LLC.
7.
Arnon, D.S., Collins, G.E., and McCallum, S.1984. Cylindrical algebraic decomposition I: The basic algorithm . SIAM J. Computing13(4):865-877.
8.
Arnon, D.S., Collins, G.E., and McCallum, S.1984. Cylindrical algebraic decomposition II: The adjacency algorithm for the plane. SIAM J. Computing13(4):878-889.
9.
Austern, M.1999. Generic Programming and the STL- Using and Extending the C++ Standard Template Library. Addison-Wesley.
10.
Barraquand, J., Kavraki, L.E., Latombe, J.C., Li, T.-Y., Motwani, R., and Raghavan, P.1997. A random sampling scheme for robot path planning. InternationalJ. Robot. Res. 16(6):759-774.
11.
Böhringer, K.-F., Donald, B., and Halperin, D.1999. On the area bisectors of a polygon. Discrete Computational Geom. 22:269-285.
12.
Böhringer, K.-F., Donald, B.R., and MacDonald, N.C.1996. Upper and lower bounds for programmable vector fields with applications to MEMS and vibratory plate part feeders. In Algorithms for Robotic Motion and Manipulation, eds. J.-P. Laumond and M. H. Overmars , 255-276. Wellesley, MA: A. K. Peters.
13.
Boissonnat, J.-D., and Preparata, F.P.1997. Robust plane sweep for intersecting segments. Report TR 3270, INRIA, Sophia Antipolis.
14.
Boissonnat, J.-D., and Snoeyink, J.2000. Efficient algorithms for line and curve segment intersection using restricted predicates. Computational Geom. Theory Appl . 16(1):35-52.
15.
Boissonnat, J.-D., and Yvinec, M.1998. Algorithmic Geometry. Cambridge University Press, UK.
16.
Brönniman, H., Kettner, L., Schirra, S., and Veltkamp, R.1998. Applications of the generic programming paradigm in the design of CGAL. Technical Report MPI-I-98-1-030, Max -Planck-Insitut für Informatik, 66123 Saarbrücken, Germany.
17.
Brönnimann, H., Emiris, I., Pan, V., and Pion, S.1999. Sign determination in Residue Number Systems. Theoret. Computer Sci. 210(1):173-197. Special Issue on Real Numbers and Computers.
18.
Brönnimann, H., and Yvinec, M.2000. Efficient exact evaluation of signs of determinants . Algorithmica27:21-56.
19.
Burnikel, C., Fleischer, R., Mehlhorn, K., and Schirra, S.1999. Efficient exact geometric computation made easy . In Proc. 15th Annual ACM Symposium Computational Geom., pp. 341-350.
20.
Burnikel, C., Fleischer, R., Mehlhorn, K., and Schirra, S.2000. A strong and easily computable separation bound for arithmetic expressions involving radicals. Algorithmica27(1):87-99.
21.
Burnikel, C., Mehlhorn, K., and Schirra, S.1994. On degeneracy in geometric computations. In Proc. 5th ACM-SIAM Symposium Discrete Algorithms, pp. 16-23.
22.
Canny, J.1987. The Complexity of Robot Motion Planning. ACM-MIT Press Doctoral Dissertation Award Series. Cambridge, MA : MIT Press.
23.
Canny, J., Donald, B.R., and Ressler, E.K.1992. A rational rotation method for robust geometric algorithms . In Proc. 8th Annual ACM Symposium Computational Geom., pp. 251- 260.
24.
The CGAL User Manual, Release 2.3. 2001 . www.cgal.org.
25.
Clarkson, K.L.1992. Safe and effective determinant evaluation. In Proc. 33rd Annual IEEE Symposium Found. Computer Sci., 387-395.
26.
de Berg, M., Guibas, L.J., and Halperin, D.1996. Vertical decompositions for triangles in 3-space . Discrete Computational Geom.15:35-61.
27.
de Berg, M., Halperin, D., Overmars, M., and van Kreveld, M.1997. Sparse arrangements and the number of views of polyhedral scenes. International J. Computational Geom. Appl . 7:175-195.
28.
de Berg, M., Katz, M.J., van der Stappen, A.F., and Vleugels, J.1997. Realistic input models for geometric algorithms . In Proc. 13th Annual ACM Symposium Computational Geom., pp. 294-303.
29.
de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O.1997. Computational Geometry: Algorithms and Applications . Heidelberg, Germany: Springer-Verlag .
30.
Devillers, O., and Preparata, F.P.1998. A probabilistic analysis of the power of arithmetic filters . Discrete amd Computational Geometry20:523-547.
31.
Edelsbrunner, H.1987. Algorithms in Combinatorial Geometry, volume 10 of EATCS Monographs on Theoretical Computer Science. Heidelberg , West Germany: Springer-Verlag.
32.
Edelsbrunner, H., and Mücke, E.P.1990. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graph . 9(1):66-104.
33.
Elber, G., and Kim, M.-S., eds. 1999. Special Issue of Computer Aided Design: Offsets, Sweeps and Minkowski Sums, vol. 31.
34.
Emiris, I.Z., Canny, J.F., and Seidel, R.1997. Efficient perturbations for handling geometric degeneracies . Algorithmica19(1-2):219-242.
35.
Fabri, A., Giezeman, G., Kettner, L., Schirra, S., and Schönherr, S.1996. The CGAL kernel: A basis for geometric computational . In Proc. 1st ACM Workshop on Appl. Computer Geom , vol. 1148 of Lecture Notes Computer Sci., eds. M. C. Lin and D. Manocha, 191-202. Springer-Verlag .
36.
Fabri, A., Giezeman, G., Kettner, L., Schirra, S., and Schönherr, S.2000. On the design of CGAL, the Computational Geometry Algorithms Library. Software-Practice and Experience30:1167-1202.
37.
Fjällström, P.-O., Petersson, J., Nilsson, L., and Zhong, Z.1998. Evaluation of range searching methods for contact searching in mechanical engineering. InternationalJ. Computational Geom. Appl. 8:67-83.
38.
Flato, E.2000. Robust and efficient construction of planar Minkowski sums. Master's thesis, Dept. Computer Sci., Tel-Aviv Univ. http://www.cs.tau.ac.il/∼flato.
39.
Flato, E., and Halperin, D.2000. Robust and efficient construction of planar Minkowski sums. In Abstracts 16th European Workshop Computational Geom ., pp. 85-88. Eilat.
40.
Flato, E., Halperin, D., Hanniel, I., Nechushtan, O., and Ezra, E.2000. The design and implementation of planar maps in CGAL. The ACM Journal of Experimental Algorithmics 5. Also in LNCS Vol. 1668 (WAE '99), Springer, pp. 154- 168.
41.
Fortune, S., and Van Wyk, C.J.1996. Static analysis yields efficient exact integer arithmetic for computational geometry. ACM Trans. Graph. 15(3):223-248.
42.
Gamma, E., Helm, R., Johnson, R., and Vlissides, J.1995. Design Patterns-Elements of Reusable Object-Oriented Software . Addison-Wesley.
43.
Geismann, N., Hemmer, M., and Schömer, E.2001. Computing a 3-dimensional cell in an arrangement of quadrics: Exactly and actually! In Proc. 17th Annual ACM Symposium Computational Geom pp. 264-273.
44.
Goodman, J. E., and O'Rourke, J., eds. 1997. Handbook of Discrete and Computational Geometry. Boca Raton, FL: CRC Press LLC.
45.
Goodrich, M., Guibas, L.J., Hershberger, J., and Tanenbaum, P.1997. Snap rounding line segments efficiently in two and three dimensions. In Proc. 13th Annual ACM Symposium Computational Geom., pp. 284-293.
46.
Granlund, T.2000. GNU MP, The GNU Multiple Precision ArithmeticLibrary, Edition 3.1.1.
47.
Greene, D.H., and Yao, F.F.1986. Finite-resolution computational geometry. In Proc. 27th Annual IEEE Symposium Found. Computational Sci, pp. 143-152.
48.
Halperin, D.1994. Robot motion planning and the single cell problem in arrangements . Journal of Intelligent and Robotic Systems11:45-65.
49.
Halperin, D.1997. Arrangements. In Handbook of Discrete and Computational Geometry, eds. J. E. Goodman and J. O'Rourke, chap. 21, 389-412. Boca Raton, FL: CRC Press LLC.
50.
Halperin, D., Latombe, J.-C., and Wilson, R.H.2000. A general framework for assembly planning: The motion space approach. Algorithmica26:577-601.
51.
Halperin, D., and Overmars, M.H.1998. Spheres, molecules and hidden surface removal. Computational Geom. Theory Appl. 11:83-102.
52.
Halperin, D., and Packer, E.2001. Iterated snap rounding. To appear in Computational Geometry: Theory and Applications. A preliminary version appeared in Abstracts 17th European Workshop Computational Geom. Berlin.
53.
Halperin, D., and Sharir, M.1995. Arrangements and their applications in robotics: Recent developments. In Proc. Workshop Algorithmic Found. Robot ., eds. K. Goldberg, D. Halperin, J.-C. Latombe , and R. Wilson, 495-511. Wellesley, MA : A. K. Peters.
54.
Halperin, D., and Shelton, C.R.1998. A perturbation scheme for spherical arrangements with application to molecular modeling. Computational Geom. Theory Appl. 10:273- 287.
55.
Hanniel, I.2000. The design and implementation of planar arrangements of curves in CGAL. M.Sc. thesis, Dept. Computer Sci., Tel Aviv University, Tel Aviv, Israel.
56.
Hanniel, I., and Halperin, D.2000. Two-dimensional arrangements in CGAL and adaptive point location for parametric curves. In Proc. of the 4th Workshop of Algorithm Engineering, vol 1982 of Lecture Notes Computer Sci, pp. 171-182. Springer-Verlag .
57.
Hobby, J.1999. Practical segment intersection with finite precision output . Computer Geom. Theory Appl. 13:199-214.
58.
Hsu, D., Kavraki, L.E., Latombe, J.-C., Motwani, R., and Sorkin, S.1998. On finding narrow passages with probabilistic roadmap planners. In Proc. 3rd Workshop Algorithmic Found. Robot., eds. P. Agarwal, L. Kavraki, and M. Mason , 141-153. Wellesley, MA: A. K. Peters.
59.
Jones, W.D.Computational geometry, a community bibliography. Overview at compgeom.cs.uiuc.edu/″jeffe/compgeom/.
60.
Karamcheti, V., Li, C., Pechtchanski, I., and Yap, C.1999. A core library for robust numeric and geometric computation . In 15th ACM Symp. on Computational Geometry, 1999, pp. 351-359.
61.
Karasick, M., Lieber, D., and Nackman, L.R.1991. Efficient Delaunay triangulations using rational arithmetic . ACM Trans. Graph. 10(1):71-91.
62.
Kaul, A., O'Connor, M.A., and Srinivasan, V.1991. Computing Minkowski sums of regular polygons. In Proc. 3rd Canad. Conf. Computational Geom., pp. 74-77.
63.
Kavraki, L., Svestka, P., Latombe, J., and Overmars, M.1996. Probabilistic roadmaps for fast path planning in high dimensional configuration spaces. IEEE Tr. on Rob. and Autom . 12:566-580.
64.
Kettner, L.1998. Designing a data structure for polyhedral surfaces . In Proc. 14th Annual ACM Symposium Computational Geom., pp. 146-154.
65.
Keyser, J., Culver, T., Manocha, D., and Krishnan, S.1999. MAPC: A library for efficient manipulation of algebraic points and curves. In Proc. 15th Annual ACM Symposium Computational Geom., pp. 360-369. http://www.cs.unc.edu/″geom/MAPC/ .
66.
Latombe, J.-C.1991. Robot Motion Planning. Boston : Kluwer Academic Publishers.
67.
Li, C., and Yap, C.2001. A new constructive root bound for algebraic expressions . In 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 496-505.
68.
Mehlhorn, K., Näher, S., Seel, M., and Uhrig, C.1999. The LEDA User Manual, Version 4.1. Max-Planck-Insitut für Informatik, 66123 Saarbrücken, Germany.
69.
Melhorn, K., and Näher, S.1999. The LEDA Platform of Combinatorial and Geometric Computing . Cambridge University Press.
70.
Milenkovic, V.1988. Verifiable implementations of geometric algorithms using finite precision arithmetic. In Geometric Reasoning, eds. D. Kapur and J. L. Mundy.North-Holland, Amsterdam , Netherlands.
71.
Mulmuley, K.1994. Computational Geometry: An Introduction Through Randomized Algorithms. Englewood Cliffs, NJ: Prentice Hall.
72.
Neagu, M., and Lacolle, B.1998. Computing the combinatorial structure of arrangements of curves using polygonal approximations. In Abstracts 14th European Workshop Computational Geom., pp. 121-123.
73.
Overmars, M.H.1996. Designing the Computational Geometry Algorithms Library CGAL. In Proc. 1st ACM Workshop on Appl. Computational Geom., vol. 1148 of Lecture Notes Computer Sci, pp. 113-119. Springer-Verlag .
74.
Preparata, F.P., and Shamos, M.I.1985. Computational Geometry: An Introduction. New York, NY: Springer-Verlag.
75.
Raab, S.1999. Controlled perturbation for arrangements of polyhedral surfaces with application to swept volumes. M.Sc. thesis, Dept. Computer Sci., Bar Ilan University, Ramat Gan , Israel.
76.
Raab, S.1999. Controlled perturbation of arrangements of polyhedral surfaces with application to swept volumes. In Proc. 15th Annual ACM Symposium Computer Geom, pp. 163-172.
77.
Raab, S., and Halperin, D.2001. Controlled perturbation for arrangements of polyhedral surfaces. Full version, manuscript, Tel Aviv University .
78.
Sack, J.-R., and Urrutia, J., eds. Handbook of Computational Geometry. North-Holland.
79.
Schirra, S.1999. Robustness and precision issues in geometric computation . In Handbook of Computational Geometry, ed. J.-R. Sack and J. Urrutia , 597-632. North-Holland, Amsterdam: Elsevier Science Publishers B.V.
80.
Schorn, P.1991. Robust algorithms in a program library for geometric computation . Ph.D. thesis, ETH Zürich , Switzerland. Report 9519.
81.
Schwartz, J.T., and Sharir, M.1983. On the "piano movers" problem II: General techniques for computing topological properties of real algebraic manifolds. Adv. Appl. Math. 4:298-351.
82.
Seidel, R.1991. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Computational Geom. Theory Appl. 1(1):51-64.
83.
Seidel, R.1998. The nature and meaning of perturbations in geometric computing . Discrete Computer Geom. 19:1-17.
84.
Sharir, M., and Agarwal, P.1995. Davenport-Schinzel Sequences and Their Geometric Applications . Cambridge University Press.
85.
Shaul, H., and Halperin, D.2002. Improved construction of vertical decompositions of three-dimensional arrangements. In Proc. 18th ACM Symp. on Computational Geom. 2002, pp. 283-292.
86.
Shewchuk, J.1997. Adaptive robust floating-point arithmetic and fast robust geometric predicates. Discrete Computational Geom. 18:305-363.
87.
Sugihara, K.1989. On finite-precision representations of geometric objects . J. Computer Syst. Sci. 39:236-247.
88.
van der Stappen, A.F.1994. Motion Planning Amidst Fat Obstacles. Ph.D. dissertation, Dept. Computer Sci., Utrecht Univ., Utrecht, Netherlands.
89.
van der Stappen, A.F., Halperin, D., and Overmars, M.H.1993. The complexity of the free space for a robot moving amidst fat obstacles. Computational Geom. Theory Appl. 3:353-373.
90.
Wilmarth, S., Amato, N., and Stiller, P.1999. Motion planning for a rigid body using random networks on the medial axis of the free space. In 15th ACM Symp. on Computational Geometry, 1999, 173-180.
91.
Yap, C.K.1990. A geometric consistency theorem for a symbolic perturbation scheme. J. Computer Syst. Sci. 40(1):2- 18.
92.
Yap, C.K.1997. Robust geometric computation. In Handbook of Discrete and Computational Geometry, eds. J. E. Goodman and J. O'Rourke, chap. 35, 653-668. Boca Raton, FL: CRC Press LLC.
93.
Yap, C.K.1997. Towards exact geometric computation. Computational Geom. Theory Appl. 7(1):3-23.
