CS531
Computational Geometry

Instructor: Tamal K. Dey
Content Description : In this course we will go through different fundamental geometric problems and structures that appear in various applications. We will study their combinatorial structures and effficient algorithms known to solve them. In this regard, we will go over segment trees, point location, planar graphs, polygon triangulation, convex hull, Voronoi diagrams, Delaunay triangulations, simplicial complexes, line/plane arrangements, curve/surface reconstructions, mesh generations, and introduction to topological data analysis.
Objectives

Be familiar with topics in geoemtric structures and algorithms such as the ones listed above
Be familiar with how to design algorithms for geometric problems with techniques listed above
Master a subset of algorithms: Convex hull, Delaunay triangulations, Curve/Surface reconstructions, Topological Data analysis
Be familiar with how to research the background of a topic in geoemtric algorithms

Computational Geometry, Algorithms and Applications, Springer, M. de Berg, M. van Kreveld, M. Overmars, O, Schwarzkopf
Discrete and Computational Geometry, Princeton U. Press, S. L. Devadoss and J. O' Rourke
Delaunay Mesh Generation, CRC Press, S.-W. Cheng, T. K. Dey and S. R. Shewchuk
Curve and Surface Reconstruction, Cambridge Press, T. K. Dey
Computational Topology for Data Analysis, Cambridge U. Press, T. K. Dey and Y. Wang

Materials (We use the notes (written by Edelsbrunner denoted E-notes and my own notes denoted D-notes and some other resources indicated appropariately.)

Topics	Notes/chapters posted on this web-page may be useful
1. Basic geometric algorithms	a. Predicates/Dualities [Note from Mount's lecture][Slides from Sacks]
	b. Segment trees [E-note] c. Point location [E-note]
	d. Planar graphs [E-note]
	e. Polygon triangulation [E-note], also see Chapter 3 in book

2. Convex Hull	a. Algorithms (2D) [E-note] b. More on convex hull [Note from Mount's lecture]
3. Simplicial complexes	a. Definitions, properties [E-note] b. More [D-note]
4. Voronoi/Delaunay	a. Voronoi diagram [E-note] [D-note from CDS book] b. Delaunay triangulation [E-note] [D-note on 3D Delaunay from CDS book] c. Edge flipping [E-note] d. Alpha shapes [E-note] e. Lifting [E-note]
5. Arrangements	a. Line/plane arrangements [E-note] b. Many faces, k-levels [Link] c. Topological sweep [E-note] d. Euler/Gauss-Bonnet for polyhedra [E-note][D-note]
6. Curve/surface reconstruction	a. Basics of curves and surfaces [D-note] b. Medial axis, sampling [D-note] c. Curve recosntruction [D-note] d. Surface recosntruction [D-note]
7. Mesh generation	a. Delaunay meshing (2D) [D-note from CDS Meshbook(CDS)] b. Delaunay meshing of surfaces/volumes I [D-note from CDS Meshbook]
8. Mesh simplification	a. Collapsings[E-note] b. Link condition and topology simplification [E-note]
9. Clustering	a. K-means clustering [D-note] b. Other clustering [D-note] c. More clustering [D-note]
10. Topological data analysis	a. Simplicial homology [D-note] b. Persistent homology [D-note] c. Persistence algorithm [D-note]

Last updated 12/21/23