Computational Geometry - SS 23
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).
- 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.
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 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.
- 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.
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
Discord: https://discord.gg/YGUZFxf 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 |
|---|---|
| 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 of arbitrary polylines (aspect ratio of traingles), variants & generalizations of quadtrees/octrees, storage and implemenation, |
| 3. | Applications of quadtrees: fast Boolean operations on B/W images, image compression, isosurfaces: definition, marching cubes, acceleration using octrees; interlude: the span space for solving 1D stabbing queries; isosurfaces for time-varying scalar fields. |
| 4. | Algorithms for the Closest Pairs problem: 2 dimensions, d dimensions |
| 5. |
Kd-Trees: definition, construction, complexity of the construction, variants of kd-trees,
nearest-neighbor (NN) search using kd-trees,
Four-dimensional geometric thinking. Curse of dimensionality. Approximate nearest neighbor (ANN) search: algorithm, correctness, time complexity; "best" ANN algorithms (randomized kd-tree, PCA-RKD, RKD forest) |
| 6. | Collisions and Spheres: collision detection, sphere packings, protosphere; inner sphere trees, kDet, protosphere, inner sphere trees, collisions with point clouds, theoretic bounds on colliding spheres. |
| 7. | Applications of kd-trees: stackless kd-tree traversal using roped kd-trees (for ray-tracing), k-NN classification, texture synthesis, statistical shape matching: surflet pair histograms, iterative closest points (ICP), |
| 7. | BSP-Trees: definitions, examples, construction algorithm, complexity of BSPs (expected size and construction time), BSPs as representation of polyhedra, simple applications of BSPs (ray shooting, point location in closed polyhedra, back-to-front rendering), deferred distribution-optimized (self-organizing) BSP trees, |
| 8. | Kinetic data structures (see the slides): motivation,, definitions, the algorithmic technique in general, performance measures for KDS, tournament tree (kinetic heap), |
| 9. | Bounding volume hierarchies (some parts were presented on slides): definition of BVHs, different types of BVs, tightness metrics for BVs, top-down construction (with PCA transformation and sweep plane technique), surface area heuristic (SAH), construction in span-space using kd-trees, efficiency of bounding boxes as BVs for neighbor filtering, |
| 10. | Convex hulls: definition, constructive proof for CH over sets of points, lower bound on complexity, convex combinations and properties of convex hulls, construction in 2D (Graham's scan), Chan's output sensitive algorithm, Euler's equation and its application to polyhedra, construction of the CH in 3D (Clarkson-Shor's algorithm), Akl-Toussaint heuristic for convex hulls, applications of convex hulls (biology, onion peeling, coll.det.). |
| 11. | Voronoi diagrams (VD): definition, examples, basic properties; lemma of the expanding circle, relationship between VD's and the convex hull, complexity of the VD; generlizations (no proofs): approximate VD's using graphics hardware, other distance metrics, generalized Voronoi sites, applications: path planning, measuring the "sphere-ness" of balls, protein structure (bioinformatics), compactness of voting districts (the redistricting problem), |
| 12. | 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. |
Range Searching (1D-Fall, der Range Tree im d-dim. Fall)
Priority Search Tree); Range X-Fast-Tree, XFT-PST Range Searching auf dem Gitter (X-Fast-Tree im 1D, XFT-PST im 2D); |
Here are the
slides I presented throughout the course.
Please consider only those sections that I covered in class.
(All other slides are purely for your entertainment, in case you are interested.)
Please also note that, while some slides are rather meant for illustration,
other slides (e.g., on KDS, BVHs, and Voronoi diagrams) contain important material of the course.
Here are the slides for the chapter on
Collision detection and sphere packings
(presented by Rene.
Notes
The following table contains (handwritten) notes.
The notes named "Vanessa's" were written and are by courtesy of Vanessa Hassouna (thank you so much!),
those named "Lorenzo's" were written and are by courtesy of Lorenzo d'Eusebio (thank's so much to you, too!),
those named "iPad" are my writing on the iPad during the online lecture (Corona semester SS 2021),
and those called "Manuscript" is my personal manuscript I use during the lecture (which is only in German, sorry!).
Note: YMMV, since I haven't checked the notes for correctness! (except mine, of course)
Also, please note that the definitive set of material for your exam is given by the table above, not by the table of notes (below)!
| Topic | Vanessa's | Lorenzo's | iPad | Manuscript |
|---|---|---|---|---|
| Quadtrees, Octrees, Applications | ||||
| Closest pairs | ||||
| Kd-trees, Curse of dimensionalty, approx. nearest neighbors, applications | ||||
| Coll.det. and sphere packing | ||||
| BSP trees and applications | ||||
| Kinetic data structures, (kinetic) segment tree | ||||
| Bounding volume hierarchies | ||||
| Convex hulls | ||||
| Voronoi diagrams | ||||
| Delaunay triangulations |
Video Recordings
The following table contains video recordings of the lecture as of SS 2021 (the first "Corona semester"). Again, the definitive set of material for your exam is the table of contents above!
The videos are encoded with H.265/HEVC and should play fine with Safari and IE. With Chrome and Firefox, you might need to download the videos, or install a plugin/extension.
Literature
- Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications; Springer. (The so-called 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. See also below.
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 Online-Literature
- Geometric Data Structures for Computer Graphics
which covers some of the topics of the course.
It is protected by password, because it is a precursor
of the book.
You can get the password by sending me an email at
zach at cs.uni-bremen dot de
, or by just asking me after lectures or in my office hours.
Here is chapter 7, and the table of contents, of the book. - 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.
- 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: Thu Jul 13 17:02:47 CEST 2023