Computational Geometry  SS 21
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 course, 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.
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).
 Indepth 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.
There are no formal prerequisites for this course; it is selfcontained. It does not require knowledge of mathematics beyond high school algebra, but it does assume that students are comfortable with rigorous thinking and with proving theorems and properties of algorithms. 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.
Some of the envisioned topics (these might change a little during the semester):
 Quadtrees / octrees, texture compression, isosurfaces, terrain visualization.
 Kdtrees, 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.
 Rangetrees and prioritysearch trees, range queries on the grid.
This course is at the intersection of computational geometry and practical computer science. Therefore, we will not assign practical, but only (easy) theoretical exercises.
News
Starting Date: 20. April 16h ct
Zoom: the link will be announced in an email via Studip.
Twitch: join the channel https://www.twitch.tv/gabzach
Discord: https://discord.gg/YGUZFxf
This is meant for you to ask questions during the (live) lecture;
also, I encourage you to use this for discussions and Q&A amongst yourselves.
(Rest assured that I don't have time to "listen" in to your chatting on discord ;) )
Topics
The following table contains the topics presented in class.
Week  Topics  Notes 

1.  Quadtrees: definition, complexity of quadtrees over points, navigation in quadtrees, balanced quadtrees, complexity of balancing operation, meshing for integer polylines using quadtrees, complexities of meshing,  
2.  Quadtrees 2: meshing for arbitrary polylines (aspect ratio of traingles, Delaunay condition), variants & generalizations of quadtrees/octrees, spacefilling curves, Zorder curve, Morton codes, point location problem, storage and implemenation,  
3.  Applications of quadtrees: space carving (reconstruction of 3D objects from image sequences), image compression, isosurfaces: definition, marching cubes, acceleration using octrees; interlude: solving stabbing queries using the span space; isosurfaces for timevarying scalar fields.  
4. 
Algorithms for the Closest Pairs problem
(2 dimensions, d dimensions, probabilistic). KdTrees: definition, construction, complexity of the construction, variants of kdtrees, nearestneighbor (NN) search using kdtrees, 

5. 
Curse of dimensionality.
Fourdimensional geometric thinking. Approximate nearest neighbor (ANN) search: algorithm, correctness, time complexity; "best" ANN algorithms (randomized kdtree, PCARKD, RKD forest), experimental results; 

6.  Applications: stackless kdtree traversal using roped kdtrees (for raytracing), kNN classification, texture synthesis, statistical shape matching (shape contexts, surflet pair histograms), iterative closest points (ICP),  
7.  BSPTrees: definition, examples, construction algorithm, complexity of BSPs (expected size and construction running time), BSPs over convex polyhedra, simple applications of BSPs (ray shooting, point location in closed polyhedra, backtofront rendering), construction of good BSPs using a cost function, deferred distributionoptimized (selforganizing) BSP trees, BSPs representing polyhedra, Boolean set operations (CSG operations) on solids using the BSP representation.  
8.  Kinetic data structures: motivation,, definitions, the algorithmic technique in general, performance measures for KDS, tournament tree (kinetic heap), epsilonapproximate KDS using epsilonkernel (just the idea), (static) segment tree (for stabbing queries), kinetic segment tree  
9.  Bounding volume hierarchies (several parts were presented on slides): definition of BVHs, different types of BVs, tightness metrics for BVs, topdown construction (with PCA transformation and sweep plane technique), surface area heuristic (SAH), construction in configurationspace using kdtrees, efficiency of bounding boxes as BVs for neighbor filtering (broad phase), computation of OBBs, application of kDOPs to collision detection, collision detection using BVHs. 
9. 
Geometric predicates: left/right, positive/negative orientation,
positive/negative volume, extremal point in a convex polygon. AklToussaint heuristic for convex hulls, Demos and applications of convex hulls (coll.det.). Voronoi diagrams (VD): definition, examples, and basic properties; lemma of the expanding circle, relationship between VD's and the convex hull, complexity of the VD. 
5. 
Sphere packings and sphere trees:
bounding volume hierarchies, simultaneous traversal,
sphere packings, the sausage catastrophe,
protosphere, inner sphere trees,
collisions with point clouds,
theoretic bounds on colliding spheres.
Hierarchical grids: kfree triangle soups, kDet 
13.  Delaunay triangulations (DT): definition of triangulations, defintion of DT's as dual of the Voronoi diagram, simple properties, Thales theorem and edge flips, theorem on the maximal minimal angle of DT's, construction of 2D Delaunay triangulations. 
14. 
Applications of VD's and DT's:
postoffice problem, connection between NNG(S) and DT(S),
connection between MST(S) and DT(S),
finding the largest empty circle. Generalizations of Voronoi diagrams (higherorder sites, power diagram, additive weights, different norms, etc.). More applications of VD's: redistricting, the cones trick for approximate VD's, Convex hulls: definition, constructive proof for CH over sets of points, construction in 2D (Graham's scan), lower bound on complexity, more properties, convex combinations, Euler's equation and application to polyhedra, construction of the CH in 3D (ClarksonShor's algorithm), Assignment meeting 
The notes named "V x" have been written and are by courtesy of Vanessa Hassouna (thank you so much!), those named "PDF" are my writing on the iPad during the online lecture.
Here are the slides I presented throughout the course. Please consider only those that I covered in class. All other slides are purely for your entertainment, in case you are interested.
Video recordings of the lecture from SS 21
Chapter  

1  MP4 
2  MP4 
3  MP4 
4  MP4 
5  MP4 
6  MP4 
7  MP4 
8  MP4 
9  MP4 
10  MP4 
11  MP4 
12  MP4 
13  MP4 
14  MP4 
15  MP4 
16  MP4 
17  MP4 
18  MP4 
Literature
 Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications; Springer. (The socalled Dutch Book) 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)
Here is an electronic preprint of the book. You will get the password on request, if you attended class.
You should also be able to find a hardcopy in the SuUB.  Satyan L. Devadoss, Joseph O'Rourke: Discrete and Computational Geometry. Princeton University Press. (chapter 1 on triangulation)
Links and OnlineLiterature
 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 nearestneighbor search in ddimensional spaces by kdtrees.
 A Tutorial on Binary Space Partitioning Trees by Bruce F. Naylor
 Introduction to Kinetic Data Structures by Leonidas Guibas (Source: Handbook of Data Structures and Applications")
Gabriel Zachmann
Last modified: Mon Jun 21 09:22:37 MDT 2021