Reference Manual

[AB99] Nina Amenta and Marshall Bern. Surface reconstruction by Voronoi filtering. Discrete Comput. Geom., 22(4):481-504, 1999.

[ADS98] Pierre Alliez, Olivier Devillers, and Jack Snoeyink. Removing degeneracies by perturbing the problem or the world. In Proc. 10th Canad. Conf. Comput. Geom., 1998.

[AKM+87] A. Aggarwal, M. M. Klawe, S. Moran, P. W. Shor, and R. Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2:195-208, 1987.

[Ale01] Andrei Alexandrescu. Modern C++ Design: Generic Programming and Design Patterns Applied. Addison-Wesley, 2001.

[AM93a] S. Arya and D. M. Mount. Algorithms for fast vector quantization. In Data Compression Conference, pages 381-390. IEEE Press, 1993.

[AM93b] S. Arya and D. M. Mount. Approximate nearest neighbor queries in fixed dimensions. In Proc. 4th ACM-SIAM Sympos. Discrete Algorithms, pages 271-280, 1993.

[And78] K. R. Anderson. A reevaluation of an efficient algorithm for determining the convex hull of a finite planar set. Inform. Process. Lett., 7(1):53-55, 1978.

[And79] A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Inform. Process. Lett., 9(5):216-219, 1979.

[AT78] S. G. Akl and G. T. Toussaint. A fast convex hull algorithm. Inform. Process. Lett., 7(5):219-222, 1978.

[Aus98] Matthew H. Austern. Generic Programming and the STL. Addison-Wesley, 1998.

[Bau75] B. G. Baumgart. A polyhedron representation for computer vision. In Proc. AFIPS Natl. Comput. Conf., volume 44, pages 589-596. AFIPS Press, Alrington, Va., 1975.

[BB97] F. Bernardini and C. Bajaj. Sampling and reconstructing manifolds using alpha-shapes. Technical Report CSD-TR-97-013, Dept. Comput. Sci., Purdue Univ., West Lafayette, IN, 1997.

[BBP01] H. Brönnimann, C. Burnikel, and S. Pion. Interval arithmetic yields efficient dynamic filters for computational geometry. Discrete Applied Mathematics, 109:25-47, 2001.

[BDH96] C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa. The Quickhull algorithm for convex hulls. ACM Trans. Math. Softw., 22(4):469-483, December 1996.

[BDP+02] Jean-Daniel Boissonnat, Olivier Devillers, Sylvain Pion, Monique Teillaud, and Mariette Yvinec. Triangulations in CGAL. Comput. Geom. Theory Appl., 22:5-19, 2002.

[BDTY00] Jean-Daniel Boissonnat, Olivier Devillers, Monique Teillaud, and Mariette Yvinec. Triangulations in CGAL. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 11-18, 2000.

[Ben75] J. L. Bentley. Multidimensional binary search trees used for associative searching. Commun. ACM, 18(9):509-517, September 1975.

[BF02] Jean-Daniel Boissonnat and Julia Flötotto. A local coordinate system on a surface. In Proc. 7th ACM Symposium on Solid Modeling and Applications, 2002.

[BFH95] Heinzgerd Bendels, Dieter W. Fellner, and Sven Havemann. Modellierung der grundlagen: Erweiterbare datenstrukturen zur modellierung und visualisierung polygonaler welten. In D. W. Fellner, editor, Modeling - Virtual Worlds - Distributed Graphics, pages 149-157, Bad Honnef / Bonn, 27.-28. November 1995.

[BMS94] C. Burnikel, K. Mehlhorn, and S. Schirra. On degeneracy in geometric computations. In Proc. 5th ACM-SIAM Sympos. Discrete Algorithms, pages 16-23, 1994.

[BPP95] Gavin Bell, Anthony Parisi, and Mark Pesce. Vrml the virtual reality modeling language: Version 1.0 specification., May 26 1995. Third Draft.

[Bro97] J. L. Brown. Systems of coordinates associated with points scattered in the plane. Comput. Aided Design, 14:547-559, 1997.

[Bur96] C. Burnikel. Exact Computation of Voronoi Diagrams and Line Segment Intersections. Ph.D thesis, Universität des Saarlandes, March 1996.

[BY98] Jean-Daniel Boissonnat and Mariette Yvinec. Algorithmic Geometry. Cambridge University Press, UK, 1998. Translated by Hervé Brönnimann.

[Byk78] A. Bykat. Convex hull of a finite set of points in two dimensions. Inform. Process. Lett., 7:296-298, 1978.

[C++98] International standard ISO/IEC 14882: Programming languages - C++. American National Standards Institute, 11 West 42nd Street, New York 10036, 1998.

[CMS93] K. L. Clarkson, K. Mehlhorn, and R. Seidel. Four results on randomized incremental constructions. Comput. Geom. Theory Appl., 3(4):185-212, 1993.

[dBvKOS97] Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, 1997.

[Dev98] Olivier Devillers. Improved incremental randomized Delaunay triangulation. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 106-115, 1998.

[Dev02] Olivier Devillers. The Delaunay hierarchy. Internat. J. Found. Comput. Sci., 13:163-180, 2002.

[DLPT98] Olivier Devillers, Giuseppe Liotta, Franco P. Preparata, and Roberto Tamassia. Checking the convexity of polytopes and the planarity of subdivisions. Comput. Geom. Theory Appl., 11:187-208, 1998.

[DP03] Olivier Devillers and Sylvain Pion. Efficient exact geometric predicates for Delaunay triangulations. In Proc. 5th Workshop Algorithm Eng. Exper., pages 37-44, 2003.

[DPT02] Olivier Devillers, Sylvain Pion, and Monique Teillaud. Walking in a triangulation. Internat. J. Found. Comput. Sci., 13:181-199, 2002.

[DT03] Olivier Devillers and Monique Teillaud. Perturbations and vertex removal in a 3D Delaunay triangulation. In Proc. 14th ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 313-319, 2003.

[Edd77] W. F. Eddy. A new convex hull algorithm for planar sets. ACM Trans. Math. Softw., 3:398-403 and 411-412, 1977.

[Ede92] H. Edelsbrunner. Weighted alpha shapes. Technical Report UIUCDCS-R-92-1760, Dept. Comput. Sci., Univ. Illinois, Urbana, IL, 1992.

[EM94] H. Edelsbrunner and E. P. Mücke. Three-dimensional alpha shapes. ACM Trans. Graph., 13(1):43-72, January 1994.

[ES96] H. Edelsbrunner and N. R. Shah. Incremental topological flipping works for regular triangulations. Algorithmica, 15:223-241, 1996.

[Far90] G. Farin. Surfaces over Dirichlet tesselations. Comput. Aided Geom. Design, 7:281-292, 1990.

[FBF77] J. H. Friedman, J. L. Bentley, and R. A. Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Softw., 3:209-226, 1977.

[FJ83] G. N. Frederickson and D. B. Johnson. Finding kth paths and p-centers by generating and searching good data structures. J. Algorithms, 4:61-80, 1983.

[FJ84] G. N. Frederickson and D. B. Johnson. Generalized selection and ranking: sorted matrices. SIAM J. Comput., 13:14-30, 1984.

[Flö03] Julia Flötotto. A coordinate system associated to a point cloud issued from a manifold: definition, properties and applications. Thèse de doctorat en sciences, Université de Nice-Sophia Antipolis, France, 2003.

[Gär99] B. Gärtner. Fast and robust smallest enclosing balls. In Proc. 7th annu. European Symposium on Algorithms (ESA), volume 1643 of Lecture Notes in Computer Science, pages 325-338. Springer-Verlag, 1999.

[GHH+03] Miguel Granados, Peter Hachenberger, Susan Hert, Lutz Ketter, Kurt Mehlhorn, and Michael Seel. Boolean operations on 3d selective nef complexes data structure, algorithms, and implementation. In Giuseppe Di Battista and Uri Zwick, editors, Algorithms - ESA 2003: 11th Annual European Symposium, volume 2832 of Lecture Notes in Computer Science, pages 174-186, Budapest, Hugary, September 2003. Springer.

[GHJV95] E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns - Elements of Reusable Object-Oriented Software. Addison-Wesley, 1995.

[Gra] Torbjörn Granlund. GMP, the GNU multiple precision arithmetic library.

[Gra72] R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Inform. Process. Lett., 1:132-133, 1972.

[Gre83] Daniel H. Greene. The decomposition of polygons into convex parts. In Franco P. Preparata, editor, Computational Geometry, volume 1 of Adv. Comput. Res., pages 235-259. JAI Press, Greenwich, Conn., 1983.

[GS85] Leonidas J. Guibas and J. Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graph., 4(2):74-123, April 1985.

[GS97a] B. Gärtner and S. Schönherr. Exact primitives for smallest enclosing ellipses. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 430-432, 1997.

[GS97b] Bernd Gärtner and Sven Schönherr. Smallest enclosing ellipses - fast and exact. Serie B - Informatik B 97-03, Freie Universität Berlin, Germany, June 1997. URL

[GS98a] Bernd Gärtner and Sven Schönherr. Smallest enclosing circles - an exact and generic implementation in C++. Serie B - Informatik B 98-04, Freie Universität Berlin, Germany, April 1998. URL

[GS98b] Bernd Gärtner and Sven Schönherr. Smallest enclosing ellipses - an exact and generic implementation in C++. Serie B - Informatik B 98-05, Freie Universität Berlin, Germany, April 1998. URL

[GS00] Bernd Gärtner and Svend Schönherr. An efficient, exact, and generic quadratic programming solver for geometric optimization. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 110-118, 2000.

[Hal97] D. Halperin. Arrangements. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 21, pages 389-412. CRC Press LLC, Boca Raton, FL, 1997.

[Han91] E. N. Hanson. The interval skip list: a data structure for finding all intervals that overlap a point. In Proc. 2nd Workshop Algorithms Data Struct., volume 519 of Lecture Notes Comput. Sci., pages 153-164. Springer-Verlag, 1991.

[HM83] S. Hertel and K. Mehlhorn. Fast triangulation of simple polygons. In Proc. 4th Internat. Conf. Found. Comput. Theory, volume 158 of Lecture Notes Comput. Sci., pages 207-218. Springer-Verlag, 1983.

[Hof89a] C. Hoffmann. Geometric and Solid Modeling. Morgan-Kaufmann, San Mateo, CA, 1989.

[Hof89b] C. M. Hoffmann. The problems of accuracy and robustness in geometric computation. IEEE Computer, 22(3):31-41, March 1989.

[Hof89c] Christoph M. Hoffmann. Geometric and Solid Modeling - An Introduction. Morgan Kaufmann, 1989.

[Hof99] M. Hoffmann. A simple linear algorithm for computing rectangular three-centers. In Proc. 11th Canad. Conf. Comput. Geom., pages 72-75, 1999.

[HS95] G. R. Hjaltason and H. Samet. Ranking in spatial databases. In M. J. Egenhofer and J. R. Herring, editors, Advances in Spatial Databases - Fourth International Symposium, number 951 in Lecture Notes Comput. Sci., pages 83-95, August 1995.

[HS00] Hisamoto Hiyoshi and Kokichi Sugihara. Voronoi-based interpolation with higher continuity. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 242-250, 2000.

[HW96] Jed Hartman and Josie Wernecke. The VRML 2.0 Handbook: Building Moving Worlds on the Web. Addison-Wesley, 1996.

[Jar73] R. A. Jarvis. On the identification of the convex hull of a finite set of points in the plane. Inform. Process. Lett., 2:18-21, 1973.

[Kar04] Menelaos I. Karavelas. A robust and efficient implementation for the segment Voronoi diagram. In Proc. Internat. Symp. on Voronoi diagrams in Science and Engineering (VD2004), 2004. To appear.

[KE02] Menelaos I. Karavelas and Ioannis Z. Emiris. Predicates for the planar additively weighted Voronoi diagram. Technical Report ECG-TR-122201-01, INRIA Sophia-Antipolis, Sophia-Antipolis, May 2002.

[KE03] Menelaos I. Karavelas and Ioannis Z. Emiris. Root comparison techniques applied to computing the additively weighted Voronoi diagram. In Proc. 14th ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 320-329, 2003.

[Ket98] L. Kettner. Designing a data structure for polyhedral surfaces. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 146-154, 1998.

[Ket99] L. Kettner. Using generic programming for designing a data structure for polyhedral surfaces. Comput. Geom. Theory Appl., 13:65-90, 1999.

[Kle89] Rolf Klein. Concrete and Abstract Voronoi Diagrams, volume 400 of Lecture Notes Comput. Sci. Springer-Verlag, 1989.

[KLPY99] Vijay Karamcheti, Chen Li, Igor Pechtchanski, and Chee Yap. The CORE Library Project, 1.2 edition, 1999.

[KM76] K. Kuratowski and A. Mostowski. Set Theory. North-Holland Publishing Co., 1976.

[Kob00] Leif Kobbelt. sqrt(3)-subdivision. In Computer Graphics (Proc. SIGGRAPH '00), volume 34, pages 103-112, 2000.

[KY02] Menelaos Karavelas and Mariette Yvinec. Dynamic additively weighted voronoi diagrams in 2d. In Proc. 10th European Symposium on Algorithms, pages 586-598, 2002.

[Män88] M. Mäntylä. An Introduction to Solid Modeling. Computer Science Press, Rockville, MD, 1988.

[Meh84] Kurt Mehlhorn. Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry, volume 3 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Heidelberg, Germany, 1984.

[Mel87] A. Melkman. On-line construction of the convex hull of a simple polyline. Inform. Process. Lett., 25:11-12, 1987.

[MN00] Kurt Mehlhorn and Stefan Näher. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge, UK, 2000.

[MNS+96] Kurt Mehlhorn, Stefan Näher, Thomas Schilz, Stefan Schirra, Michael Seel, Raimund Seidel, and Christian Uhrig. Checking geometric programs or verification of geometric structures. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 159-165, 1996.

[MNSU] K. Mehlhorn, S. Näher, M. Seel, and C. Uhrig. The LEDA User Manual. Max-Planck-Insitut für Informatik, 66123 Saarbrücken, Germany.

[MP78] D. E. Muller and F. P. Preparata. Finding the intersection of two convex polyhedra. Theoret. Comput. Sci., 7:217-236, 1978.

[MS96] David R. Musser and Atul Saini. STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library. Addison-Wesley, 1996.

[MSW92] J. Matoušek, Micha Sharir, and Emo Welzl. A subexponential bound for linear programming. In Proc. 8th Annu. ACM Sympos. Comput. Geom., pages 1-8, 1992.

[Mul90] K. Mulmuley. A fast planar partition algorithm, I. J. Symbolic Comput., 10(3-4):253-280, 1990.

[Mye95] Nathan C. Myers. Traits: a new and useful template technique. C++ Report, June 1995.

[Orl90] M. Orlowski. A new algorithm for the largest empty rectangle problem. Algorithmica, 5:65-73, 1990.

[Phi96] Mark Phillips. Geomview Manual, Version 1.6.1 for Unix Workstations. The Geometry Center, University of Minnesota, 1996.

[Pip93] B. Piper. Properties of local coordinates based on dirichlet tesselations. Computing Suppl., 8:227-239, 1993.

[Pug90] W. Pugh. Skip lists: a probabilistic alternative to balanced trees. Commun. ACM, 33(6):668-676, 1990.

[Req80] Aristides G. Requicha. Representations for rigid solids: Theory, methods, and systems. ACM Computing Surveys, 12(4):437-464, 1980.

[SA95] Micha Sharir and P. K. Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York, 1995.

[Sam90] H. Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA, 1990.

[Sch96] Michael Schutte. Zufällige konvexe mengen. Master's thesis, Freie Universität Berlin, Germany, 1996.

[Sch00] Stefan Schirra. Robustness and precision issues in geometric computation. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, chapter 14, pages 597-632. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000.

[Sei91] R. Seidel. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Comput. Geom. Theory Appl., 1(1):51-64, 1991.

[She98] Jonathan R. Shewchuk. A condition guaranteeing the existence of higher-dimensional constrained delaunay triangulations. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 76-85, 1998.

[She00] Jonathan R. Shewchuk. Mesh generation for domains with small angles. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 1-10, 2000.

[Sib80] R. Sibson. A vector identity for the Dirichlet tesselation. Math. Proc. Camb. Phil. Soc., 87:151-155, 1980.

[Sib81] R. Sibson. A brief description of natural neighbour interpolation. In Vic Barnet, editor, Interpreting Multivariate Data, pages 21-36. John Wiley & Sons, Chichester, 1981.

[Skl72] J. Sklansky. Measuring concavity on rectangular mosaic. IEEE Trans. Comput., C-21:1355-1364, 1972.

[SL95] Alexander Stepanov and Meng Lee. The standard template library., October 1995.

[SM00] M. Seel and K. Mehlhorn. Infimaximal frames: A technique for making lines look like segments. Research Report MPI-I-2000-1-005, MPI für Informatik, Saarbrücken, Germany, December 2000.

[Str97] Bjarne Stroustrup. The C++ Programming Language. Addison-Wesley, 3rd edition, 1997.

[STV+95] Christian Schwarz, Jürgen Teich, Alek Vainshtein, Emo Welzl, and Brian L. Evans. Minimal enclosing parallelogram with application. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages C34-C35, 1995.

[SVH89] B. Serpette, J. Vuillemin, and J. C. Herv`e. BigNum: a portable and efficient package for arbitrary-precision arithmetic. Technical report, INRIA, May 1989.

[SW96] Micha Sharir and Emo Welzl. Rectilinear and polygonal p-piercing and p-center problems. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 122-132, 1996.

[Tei99] Monique Teillaud. Three dimensional triangulations in CGAL. In Abstracts 15th European Workshop Comput. Geom., pages 175-178. INRIA Sophia-Antipolis, 1999.

[Tou83] G. T. Toussaint. Solving geometric problems with the rotating calipers. In Proc. IEEE MELECON '83, pages A10.02/1-4, 1983.

[Vai90] A. Vainshtein. Finding minimal enclosing parallelograms. Diskretnaya Matematika, 2:72-81, 1990. In Russian.

[vLS82] J. van Leeuwen and Anneke A. Schoone. Untangling a travelling salesman tour in the plane. In J. R. Mühlbacher, editor, Proc. 7th Internat. Workshop Graph-Theoret. Concepts Comput. Sci., pages 87-98, München, 1982. Hanser.

[VRM96] The virtual reality modeling language specification: Version 2.0, ISO/IEC CD 14772., August 4 1996.

[Wei85] K. Weiler. Edge-based data structures for solid modeling in a curved surface environment. IEEE Comput. Graph. Appl., 5(1):21-40, 1985.

[Wel91] Emo Welzl. Smallest enclosing disks (balls and ellipsoids). In H. Maurer, editor, New Results and New Trends in Computer Science, volume 555 of Lecture Notes Comput. Sci., pages 359-370. Springer-Verlag, 1991.

[Wer94] Josie Wernicke. The Inventor Mentor: Programming Object-Oriented 3D Graphics with Open Inventor, Release 2. Addison-Wesley, 1994.

[Yap97] C. Yap. Towards exact geometric computation. Comput. Geom. Theory Appl., 7(1):3-23, 1997.

[YD95] C. K. Yap and T. Dubé. The exact computation paradigm. In D.-Z. Du and F. K. Hwang, editors, Computing in Euclidean Geometry, volume 4 of Lecture Notes Series on Computing, pages 452-492. World Scientific, Singapore, 2nd edition, 1995.

[ZE02] Afra Zomorodian and Herbert Edelsbrunner. Fast software for box intersection. Int. J. Comput. Geom. Appl., 12:143-172, 2002.