Computational Geometry - SS 17
Where should you place a new cell phone transmitter in a city such that its coverage area does not overlap with other, existing cell phone transmitters? How should you connect the nodes of a height field such that you obtain a plausible 3D terrain? How can you compress images very easily and still get a decent compression rate? (JPEG achieves very good compression rates, but it also is very complex.)
In recent years, methods from computational geometry have been widely adopted in various fields of practical computer science, yielding elegant and efficient algorithms. This course aims at endowing practitioners with a working knowledge of a wide range of algorithms, methods, and tools from computational geometry. It will enable attendees to recognize geometric problems in their respective field of work and select the most suitable data structure. In the ourse, I will show this with a number of examples, which are mostly situated in the area of visual computing.
The course will focus on geometric algorithms and data structures that have proven to be versatile, efficient, fundamental, and easy to implement. Thus, students will benefit immediately from this course, if they are interested in areas such as computer graphics, computer vision, robotics, machine learning, spatial databases, visualization, simulation, and many others.
There are no formal prerequisites for this course; it is self-contained. It does not require knowledge of mathematics beyond high school algebra, but it does assume that students are comfortable with rigorous thinking, and that they not intimidated by formal proofs. If you have attended my Computer Graphics course in the Bachelor's program (CG1), then your feelings towards the chapter on triangulation can serve as an indicator whether or not this course will be interesting and rewarding to you.
This course is for you, if you want to acquire ...
- Knowledge and mastering of some of the geometric data structures that are very important for many methods in a lot of areas of practical computer science (see above).
- In-depth insights into the reasons why algorithms become very efficient by using these data structures.
- Knowledge of some applications of these data structures in visual computing.
- Some skills in proving the correctness and complexity analysis of geometric algorithms.
Some of the envisioned topics (these might change a little during the semester):
- Quadtrees / octrees, texture compression, isosurfaces, terrain visualization.
- Kd-trees, texture synthesis, point cloud surfaces,
- BSP trees, boolean operations on solids,
- Bounding volume hierarchies.
- Kinetic data structures, collision detection.
- Convex hulls.
- Voronoi and Delaunay diagrams, facility location problems, approximation to the TSP.
- Range-trees and priority-search trees, range queries on the grid.
Note: the exact combination of topics will be modified a little bit each time.
This course is at the intersection of computational geometry and practical computer science. Therefore, we will not assign practical, but only (easy) theoretical exercises.
The following table contains the topics presented in class.
|1.||Quadtrees: definition, complexity of quadtrees over points, navigation in quadtrees, balanced quadtrees, complexity of balancing operation, meshing for integer polylines using quadtrees,|
|2.||Quadtrees 2: Closest points problem, meshing for arbitrary polylines, variants of quadtrees/octrees and generalizations, storage and implemenation, space-filling curves, Morton codes,|
- Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications; Springer. Available online at Springer.
- Franco P. Preparata, Michael Ian Shamos: Computational Geometry: An Introduction; Springer
- Rolf Klein: Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen; Springer
- Joseph O'Rourke: Computational Geometry in C. Cambridge University Press
- G. Zachmann & E. Langetepe: Geometric Data Structures for Computer Graphics CRC Press, 2006, ISBN: 9781568812359 (in the past AK Peters)
- Satyan L. Devadoss, Joseph O'Rourke: Discrete and Computational Geometry. Princeton University Press. (Kapitel 1 zum Thema Triangulation)
Links and Online-Literature
- Marching Cubes Demo
- Isosurface extraction where users can define the implicit function by themselves (metaballs rendering)
- Here you can find Python code and the results of some experiments of approximate nearest-neighbor search in d-dimensional spaces by kd-trees.
- Introduction to Kinetic Data Structures by Leonidas Guibas (Source: Handbook of Data Structures and Applications")
Gabriel Zachmann Last modified: Wed Apr 19 22:58:21 CEST 2017