CS 498 TC — Computational Geometry — Spring 2021
CS 498 TC — Computational Geometry — Spring 2021
-
From Jeff Erickson
42 plays 0a. 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… -
From Jeff Erickson
41 plays 0a. 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… -
From Jeff Erickson
38 plays 0a. Halfplane discrepancy via vertex levels b. Ham-sandwich theorem via intersecting median levels. c. Open problem: Complexity of median levels / number of halving lines… -
From Jeff Erickson
52 plays 0a. Definitions and basic structure b. Motivation via duality: collinearity, angular orders, discrepancy c. Brute-force incremental construction d. The Zone Theorem -
From Jeff Erickson
46 plays 0a. 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… -
From Jeff Erickson
46 plays 0a. 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.… -
From Jeff Erickson
56 plays 0a. Examples: linear classification, star-shaped polygons b. Symbolic formulation: max {c·x | Ax ≤ b} c. Geometric formulation: Lowest point in a convex… -
From Jeff Erickson
70 plays 0a. Paraboloid lifting redux: Delaunay triangulation = projection of lower hull of points on paraboloid Voronoi diagram = projection of upper envelope planes tangent to… -
From Jeff Erickson
45 plays 0a. Sentinel triangles and symbolic infinite values b. The Delaunay history dag c. History dag analysis -
From Jeff Erickson
75 plays 0a. 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.… -
From Jeff Erickson
81 plays 0a. Voronoi diagram definitions b. Structural properties of Voronoi diagrams c. Delaunay triangulation definitions d. The in-circle primitive e. Local Delaunay vs.… -
From Jeff Erickson
55 plays 0Oops! 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… -
From Jeff Erickson
48 plays 0a. 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.… -
From Jeff Erickson
65 plays 0a. 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 -
From Jeff Erickson
49 plays 0a. Inductive proof (edge deletion) b. Easy consequences c. Analysis of trapezoidal decomposition sweeping d. Randomized incremental construction WARNING: The randomized… -
From Jeff Erickson
49 plays 0a. 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… -
From Jeff Erickson
73 plays 0a. 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… -
From Jeff Erickson
104 plays 0Zoom Recording ID: 84281611927 UUID: I7tW/yhFTPyW2Do9GgPiSA== Meeting Time: 2021-02-11T16:47:54Z -
From Jeff Erickson
100 plays 0Zoom Recording ID: 84281611927 UUID: TTr70CwzQ4aNz+hj7ww3yg== Meeting Time: 2021-02-09T16:50:56Z -
From Jeff Erickson
147 plays 0a. Line segment intersection problems b. Testing two segments = four orientation tests c. Sweep algorithm intuition d. Sweep status data structure: balanced BST using… -
From Jeff Erickson
124 plays 0a. 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 -
From Jeff Erickson
216 plays 0a. Review Jarvis March b. Graham's scan (three-penny algorithm) c. General position and 3SUM d. Chan's algorithm ("shatterhull"): Setup e. Finding… -
From Jeff Erickson
724 plays 0a. Administrivia b. What is computational geometry? c. Example: post office problem d. Example: geometric shortest paths e. Convex hulls: definitions f. Orientation test…