Departament de Matemàtica Aplicada II
Facultat d’Informàtica de Barcelona
Universitat Politècnica de Catalunya
Goal
This seminar is designed as an introduction to geometric algorithms. As the field is far too wide to fit in a short seminar, a strong selection is been done every year. The proposed contents (and related activities) intend to give:
- An idea of both the topics and the applications of the field.
- The most useful algorithmic tools in the field.
- A selection of topics intended for computer graphics students.
Contents
- Introductory material
- Convex hulls in 2D
- Voronoi diagrams and Delaunay triangulations in 2D
- Duality and its applications
- Suggested references:
- M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, Computational Geometry Algorithms and Applications, Chapter 8 and, particularly, sections 8.2 and 8.5.
- J-D. Boissonat, M. Yvinec, Algorithmic Geometry, Chapter 7 and, most specially, section 7.1.3.
- H. Edesbrunner, Algorithms in Combinatorial Geometry
- An applet to play with
- Slides by the student Marc Sunet
- Suggested references:
- Convex hulls in 3D
- Suggested references:
- M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, Computational Geometry Algorithms and Applications, sections 11.1, 11.2, 11.3 and 11.6.
- J. O’Rourke, Computational Geometry in C
- F. P. Preparata, M. I. Shamos, Computational Geometry An Introduction
- J-D. Boissonat, M. Yvinec, Algorithmic Geometry, Chapters 7, 8, and 9.
- An applet to play with
- Slides by the student Roger Hernando
- Suggested references:
- Analyzing randomized incremental algorithms: An introduction
- Voronoi diagrams and Delaunay tessellations in 3D or with restrictions
- Suggested references:
- Okabe, Boots, Sugihara, Chiu, Spatial tessellations: concepts and applications of Voronoi diagrams
- Aurenhammer, Klein, Lee, Voronoi diagrams and Delaunay triangulations
- Slides by the student Marc Comino
- Suggested references:
- Applying Voronoi diagrams and Delaunay tessellations to shape reconstruction
- Suggested references:
- Crust, anticrust, and beta-skeletons: N. Amenta, M. Bern, D. Eppstein, The Crust and the Beta-Skeleton: Combinatorial Curve Reconstruction, Graphical Models and Image Processing, Vol. 60/2, No. 2, pp. 125-135, 1998.
- Alpha-shapes: H. Edelsbrunner, D. G. Kirkpatrick, R. SeidelAurenhammer, On the Shape of a Set of Points in the Plane, IEEE Transactions on Information Theory, Vol. IT-D, No. 4, pp. 551-559, 1983.
- Alpha-shapes: H. Edelsbrunner Alpha shapes – A Survey.
- An applet to play with
- Slides by the student Miguel Ángel Vico
- Suggested references:
Resources
Computational Geometric Algorithms Library (CGAL)
Never implement a geometric algorithm before checking if CGAL has it! It is a reliable and efficient sofware!
Mathematical text editor
LaTeX is the most extended editor of scientific texts (LaTeX is used to write all the textbooks of scientific publishers as important as Springer, and also most of the mathematics and computer science conferences around the world). It’s a free source software that has versions for all operating systems. You can download LaTeX from http://www.tug.org/.
For those of you who work on windows, WinEdt is a very convenient editor for writing LaTeX code. You can download it from http://www.winedt.com/.
Drawings
Each person likes preparing his/her figures with his/her favorite drawing program. I use IPE (an evolution of xfig designed by a computational geometer), because it allows me to draw the geometric figures that I need, because it integrates text in LaTeX, and because it allows me to also prepare my presentations in a very easy what-you-see-is-what-you-get way. IPE is free source and has versions for all the operating systems. You can download it from http://ipe7.sourceforge.net/.
Geometric constructions
In addition to producing your own drawings, you may whish to create and experiment with geometric constructions. If so, we recommend GeoGebra.