Search for tag: "geometry"

23. Visibility graphs

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 sweep: O(n^2) time e.…

From  Jeff Erickson 20 plays 0  

21. Shortest paths in polygons

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 path in dual tree f. Funnel…

From  Jeff Erickson 26 plays 0  

20. Applications of line arrangements

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 c. Minimum-area triangles via…

From  Jeff Erickson 21 plays 0  

19. Line arrangements

a. Definitions and basic structure b. Motivation via duality: collinearity, angular orders, discrepancy c. Brute-force incremental construction d. The Zone Theorem

From  Jeff Erickson 35 plays 0  

18. Smallest enclosing balls

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 "LP-type" problems

From  Jeff Erickson 21 plays 0  

17. Low-dimensional linear prorgramming

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. Worst-case analysis: O(n^d)…

From  Jeff Erickson 18 plays 0  

16. Linear programming

a. Examples: linear classification, star-shaped polygons b. Symbolic formulation: max {c·x | Ax ≤ b} c. Geometric formulation: Lowest point in a convex polyhedron d. No solution: Infeasible…

From  Jeff Erickson 29 plays 0  

15. Power diagrams, anti-Voronoi diagrams, and 3D convex hulls

a. Paraboloid lifting redux: Delaunay triangulation = projection of lower hull of points on paraboloid Voronoi diagram = projection of upper envelope planes tangent to paraboloid upper envelope =…

From  Jeff Erickson 30 plays 0  

14. Randomized incremental analysis

a. Sentinel triangles and symbolic infinite values b. The Delaunay history dag c. History dag analysis

From  Jeff Erickson 27 plays 0  

13. Delaunay triangulations II

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. Randomized incremental…

From  Jeff Erickson 39 plays 0  

12'. Voronoi diagrams and Delaunay triangulations (redo)

a. Voronoi diagram definitions b. Structural properties of Voronoi diagrams c. Delaunay triangulation definitions d. The in-circle primitive e. Local Delaunay vs. Delaunay (proof next time)

From  Jeff Erickson 45 plays 0  

12. Voronoi diagrams and Delaunay triangulations

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 triangulation definitions) d.…

From  Jeff Erickson 30 plays 0  

11. History dags, point location, and fast triangulation

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. Seidel's triangulation algorithm:…

From  Jeff Erickson 21 plays 0  

10. Randomized incremental construction

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

From  Jeff Erickson 32 plays 0  

9. Euler's formula: V - E + F = 2

a. Inductive proof (edge deletion) b. Easy consequences c. Analysis of trapezoidal decomposition sweeping d. Randomized incremental construction WARNING: The randomized incremental analysis is…

From  Jeff Erickson 25 plays 0  

8. Planar maps

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 dual map G* (vertices = F*,…

From  Jeff Erickson 18 plays 0  

7. Elementary polygon algorithms

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 "shoelace" algorithm for…

From  Jeff Erickson 32 plays 0  

6. Polygon triangulation

Zoom Recording ID: 84281611927 UUID: I7tW/yhFTPyW2Do9GgPiSA== Meeting Time: 2021-02-11T16:47:54Z

From  Jeff Erickson 47 plays 0  

5. Line Segment Intersection II

Zoom Recording ID: 84281611927 UUID: TTr70CwzQ4aNz+hj7ww3yg== Meeting Time: 2021-02-09T16:50:56Z

From  Jeff Erickson 26 plays 0  

4. Line Segment Intersection

a. Line segment intersection problems b. Testing two segments = four orientation tests c. Sweep algorithm intuition d. Sweep status data structure: balanced BST using orientation tests for…

From  Jeff Erickson 56 plays 0  

3. Projective Duality

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

From  Jeff Erickson 45 plays 0  

2. More Convex Hulls

a. Review Jarvis March b. Graham's scan (three-penny algorithm) c. General position and 3SUM d. Chan's algorithm ("shatterhull"): Setup e. Finding tangents in O(log n) time f.…

From  Jeff Erickson 72 plays 0  

1. Intro and Convex Hulls

a. Administrivia b. What is computational geometry? c. Example: post office problem d. Example: geometric shortest paths e. Convex hulls: definitions f. Orientation test g. Jarvis march…

From  Jeff Erickson 248 plays 0  

Investigations in Combinatorial Game Theory

TBA

From  Philipp Hieronymi 30 plays 0