4.9. Computational Geometry and Topology (CGT)

4.9. Computational Geometry and Topology (CGT)

This area covers geometric algorithms and topological methods for processing discrete spatial data, including Voronoi structures, convex hulls, mesh generation, digital topology, and applied persistent homology, with applications to computer graphics, robotics, and scientific computing.

Table 4.9: List of KUs in the Computational Geometry and Topology area.

4.9.1. CGT/Voronoi Diagrams and Delaunay Triangulations  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Back to top

Voronoi diagrams, Delaunay triangulations, duality, algorithms, and applications in spatial computation.
Topics:
Core

  • Voronoi diagram: definition, combinatorial complexity, and properties in \(\mathbb{R}^d\)
  • Delaunay triangulation: empty circumcircle property and duality with Voronoi
  • Algorithms: Fortune's sweep-line algorithm and randomized incremental construction
  • Weighted Voronoi diagrams and power diagrams
  • Applications: nearest-neighbor search, path planning, and mesh generation

Learning Outcomes:
Core:

  1. Describe the duality between the Voronoi diagram and the Delaunay triangulation and prove the empty circumcircle property [Familiarity]
  2. Construct Voronoi diagrams and Delaunay triangulations using Fortune's algorithm and analyze their complexity [Usage]
  3. Apply Delaunay triangulations to mesh generation and nearest-neighbor queries in spatial datasets [Assessment]

4.9.2. CGT/Convex Hulls and Polytopes  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Back to top

Convex hull algorithms in 2D and 3D, convex polytopes, extreme point queries, and half-space intersection.
Topics:
Core

  • 2D convex hull algorithms: Graham scan, Jarvis march, and Chan's algorithm
  • 3D convex hull: incremental construction and randomized algorithms
  • Convex polytopes: face lattice, Euler's relation, and the upper bound theorem
  • Half-space intersection and duality between convex hull and half-space problems
  • Applications: linear programming, collision detection, and shape analysis

Learning Outcomes:
Core:

  1. Compare the time complexity of Graham scan, Jarvis march, and Chan's algorithm and identify optimal cases [Familiarity]
  2. Implement a 2D convex hull algorithm and extend it to the 3D incremental construction [Usage]
  3. Apply duality between convex hull and half-space intersection to solve linear programming problems geometrically [Assessment]

4.9.3. CGT/Digital Topology and Image Analysis  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Back to top

Topological properties of digital images, connected components, thinning, skeletonization, and topological persistence in image data.
Topics:
Core

  • Digital adjacency, connectivity, and the Jordan curve theorem for digital images
  • Connected component labeling and topological invariants of binary images
  • Thinning algorithms and medial axis skeletonization
  • Euler characteristic of digital objects and its computation from local patterns

Non Core

  • Topological methods for image segmentation and surface reconstruction from point clouds

Learning Outcomes:
Core:

  1. Explain digital adjacency and why inconsistent connectivity leads to topological paradoxes [Familiarity]
  2. Apply thinning and skeletonization algorithms to extract structural features from binary images [Usage]

NonCore:

  1. Compute topological invariants (Euler characteristic, Betti numbers) of a digital object and use them for shape classification [Assessment]

4.9.4. CGT/Persistent Homology and Applied Topology  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Back to top

Simplicial homology, filtrations, persistence modules, barcodes, and applications to shape analysis and data.
Topics:
Core

  • Simplicial homology: chain groups, boundary operators, and Betti numbers
  • Persistence modules and the structure theorem for decomposition into interval modules
  • Barcodes and persistence diagrams: birth-death pairs and topological lifetime
  • Algorithms for persistent homology: the boundary matrix reduction algorithm

Non Core

  • Applications: protein folding, materials science, and neuroscience (2020-2025)

Learning Outcomes:
Core:

  1. Compute simplicial homology groups and Betti numbers from a simplicial complex [Familiarity]
  2. Construct a filtration from a point cloud and compute its persistence diagram using boundary matrix reduction [Usage]

NonCore:

  1. Interpret barcodes of real data and explain the topological features they reveal in a scientific context [Assessment]

4.9.5. CGT/Mesh Generation and Geometric Algorithms  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Back to top

Triangular and tetrahedral mesh generation, Delaunay refinement, quality metrics, and algorithms for spatial subdivision.
Topics:
Core

  • Mesh quality metrics: aspect ratio, minimum angle, and circumradius-to-shortest-edge ratio
  • Delaunay refinement: Ruppert's algorithm and Shewchuk's algorithm for quality mesh generation
  • Tetrahedral mesh generation: constrained Delaunay tetrahedralization and Steiner points
  • Quad and hex-dominant meshing: cross-field methods and polyhedral meshes

Non Core

  • Adaptive mesh refinement driven by error estimators in finite element simulations

Learning Outcomes:
Core:

  1. Explain the Delaunay refinement strategy and the role of Steiner points in achieving quality guarantees [Familiarity]
  2. Generate a quality constrained Delaunay triangulation for a given planar domain using Ruppert's algorithm [Usage]

NonCore:

  1. Design an adaptive mesh refinement strategy for a PDE problem and justify refinement criteria based on a posteriori error estimates [Assessment]

Spotted a typo, an outdated course, a broken link, or have a suggestion? Let us know.

Scan to open on your phone