CS 498 TC — Computational Geometry — Spring 2021
CS 498 TC — Computational Geometry — Spring 2021
-
a. Definitions; application to shortest paths b. Rotational sweep at each vertex: O(n^2 log n) time c. Dual interpretation as sweep over line arrangement d. Topological…
23. Visibility graphs
From Jeff Erickson
42 plays 0 -
a. Setup and motivation b. Structure: polygonal path through reflex vertices c. Greedy improvement d. Crosses any diagonal at most once. e. Sleeve: triangles dual to…
21. Shortest paths in polygons
From Jeff Erickson
42 plays 0 -
a. Halfplane discrepancy via vertex levels b. Ham-sandwich theorem via intersecting median levels. c. Open problem: Complexity of median levels / number of halving lines…
20. Applications of line arrangements
From Jeff Erickson
38 plays 0 -
a. Definitions and basic structure b. Motivation via duality: collinearity, angular orders, discrepancy c. Brute-force incremental construction d. The Zone Theorem
19. Line arrangements
From Jeff Erickson
54 plays 0 -
a. Not LP, but LP enough. b. Existence and uniqueness (via convexity) c. Pivoting lemma d. Welzl's MiniDisk algorithm (≈ Seidel's LP algorithm) e. Other…
18. Smallest enclosing balls
From Jeff Erickson
47 plays 0 -
a. Input: halfspaces H and partial basis (planes) B b. Sentinel constraints c. Incremental algorithm d. Correctness: violated constraint must be in the optimal basis e.…
17. Low-dimensional linear prorgramming
From Jeff Erickson
47 plays 0 -
a. Examples: linear classification, star-shaped polygons b. Symbolic formulation: max {c·x | Ax ≤ b} c. Geometric formulation: Lowest point in a convex…
16. Linear programming
From Jeff Erickson
57 plays 0 -
a. Paraboloid lifting redux: Delaunay triangulation = projection of lower hull of points on paraboloid Voronoi diagram = projection of upper envelope planes tangent to…
15. Power diagrams, anti-Voronoi diagrams, and 3D…
From Jeff Erickson
80 plays 0 -
a. Sentinel triangles and symbolic infinite values b. The Delaunay history dag c. History dag analysis
14. Randomized incremental analysis
From Jeff Erickson
47 plays 0 -
a. Local Delaunay = global Delaunay proof b. Lawson's flip algorithm c. Linearization: paraboloid lifting map d. Analysis of Lawson's algorithm: O(n^2) time e.…
13. Delaunay triangulations II
From Jeff Erickson
79 plays 0 -
a. Voronoi diagram definitions b. Structural properties of Voronoi diagrams c. Delaunay triangulation definitions d. The in-circle primitive e. Local Delaunay vs.…
12'. Voronoi diagrams and Delaunay…
From Jeff Erickson
85 plays 0 -
Oops! I forgot to hit the record button until 55 minutes into the lecture. (a. Voronoi diagram definitions) (b. Structural properties of Voronoi diagrams) (c. Delaunay…
12. Voronoi diagrams and Delaunay triangulations
From Jeff Erickson
56 plays 0 -
a. History dag description b. Space analysis: O(n) expected c. Query time analysis: O(log n) expected d. Polygon triangulation: locating vertices by scanning e.…
11. History dags, point location, and fast…
From Jeff Erickson
53 plays 0 -
a. Overview: O(n) expected total update time b. Conflict list description c. Conflict list analysis: O(n log n) expected total update time d. History dag description
10. Randomized incremental construction
From Jeff Erickson
66 plays 0 -
a. Inductive proof (edge deletion) b. Easy consequences c. Analysis of trapezoidal decomposition sweeping d. Randomized incremental construction WARNING: The randomized…
9. Euler's formula: V - E + F = 2
From Jeff Erickson
52 plays 0 -
a. Definitions (planar graphs, planar maps, planar straight-line graphs) b. Adjacency/incidence lists c. PLSGs: half-edges, vertex coordinate, and faces d. Kitty! e. The…
8. Planar maps
From Jeff Erickson
52 plays 0 -
a. Point in polygon: ray crossing parity b. Winding number: sum of signed ray crossings c. Alexander numbering d. Fast and Loose / The Endless Chain e. Gauss's…
7. Elementary polygon algorithms
From Jeff Erickson
76 plays 0 -
Zoom Recording ID: 84281611927 UUID: I7tW/yhFTPyW2Do9GgPiSA== Meeting Time: 2021-02-11T16:47:54Z
6. Polygon triangulation
From Jeff Erickson
112 plays 0 -
Zoom Recording ID: 84281611927 UUID: TTr70CwzQ4aNz+hj7ww3yg== Meeting Time: 2021-02-09T16:50:56Z
5. Line Segment Intersection II
From Jeff Erickson
101 plays 0 -
a. Line segment intersection problems b. Testing two segments = four orientation tests c. Sweep algorithm intuition d. Sweep status data structure: balanced BST using…
4. Line Segment Intersection
From Jeff Erickson
158 plays 0 -
a. Points are pairs of numbers, but so are lines b. The upper envelope problem c. Merge-envelope d. Select-envelope e. Point-line duality dictionary
3. Projective Duality
From Jeff Erickson
128 plays 0 -
a. Review Jarvis March b. Graham's scan (three-penny algorithm) c. General position and 3SUM d. Chan's algorithm ("shatterhull"): Setup e. Finding…
2. More Convex Hulls
From Jeff Erickson
228 plays 0 -
a. Administrivia b. What is computational geometry? c. Example: post office problem d. Example: geometric shortest paths e. Convex hulls: definitions f. Orientation test…
1. Intro and Convex Hulls
From Jeff Erickson
764 plays 0
Search for ""