|
Straight-line planar embedding, star-shaped-hole filling, canonical ordering, Schnyder woods, grid embedding
Date of creation
2/17/2023 6:00 AM
|
|
Toby Stafford (University of Manchester) presents at the Facets of Noncommutative Geometry conference, hosted at the University of Illinois Champaign-Urbana on June 11, 2022.
Date of creation
6/12/2022 5:00 AM Video credits
Jennifer Nygard
|
|
Travis Schedler (Imperial College London) presents at the Facets of Noncommutative Geometry conference, hosted at the University of Illinois Champaign-Urbana on June 11, 2022.
Date of creation
6/12/2022 5:00 AM Video credits
Jennifer Nygard
|
|
Susan Sierra (University of Edinburgh) presents at the Facets of Noncommutative Geometry conference, hosted at the University of Illinois Champaign-Urbana on June 11, 2022.
Date of creation
6/11/2022 5:00 AM Video credits
Jennifer Nygard
|
|
Gwyn Bellamy (University of Glasgow) presents at the Facets of Noncommutative Geometry conference, hosted at the University of Illinois Champaign-Urbana on June 11, 2022.
Date of creation
6/11/2022 5:00 AM Video credits
Jennifer Nygard
|
|
Visibility graph definitions Complexity: Θ(n) best case, Θ(n^2) worst case Construction via sweep of dual line arrangement: O(n^2 log n) time Four types of events Topological sweep:…
Date of creation
4/22/2022 5:00 AM
|
|
Decision problem: Free space is convex in each cell Weak Fréchet distance: Replace free space in each cell with convex hull of free boundary segments Finding reachable points on grid boundary…
|
|
Convolution A*B definition Minkowski sum A+B = points where A*B has positive winding number Fréchet distance definition (minimum leash length) Discrete Fréchet distance via dynamic…
Date of creation
4/15/2022 5:00 AM
|
|
The translational motion planning problem Work space, configuration space, and free space Minkowski sum definition and naive construction Example with complexity Θ(m^2 n^2) Convex + convex =…
Date of creation
4/13/2022 5:00 AM
|
|
Definitions: Shortest paths in polygons Rubber-band structure Incremental improvement Crossing structure The funnel algorithm Variant: Given crossing sequence instead of explicit coordinates …
Date of creation
4/8/2022 5:00 AM
|
|
Halfplane discrepancy Ham sandwich cuts Minimum-area triangles and affine degeneracy 3SUM and 3SUM-hardness
Date of creation
4/6/2022 5:00 AM
|
|
Definitions Motivation Incremental algorithm: For each line, trace the zone in the arrangement of earlier lines The Zone Theorem
Date of creation
4/1/2022 5:00 AM
|
|
Smallest enclosing annulus: reduce to LP by linearization Smallest enclosing ball: Can't be linearized! Welzl's MinDisk algorithm Proof of solution uniqueness Proof of pivoting/exchange…
Date of creation
3/30/2022 5:00 AM
|
|
Set up and assumptions Seidel's incremental LP algorithm Proof of the exchange lemma Worst-case analysis of violation tests and basis computations Randomized analysis of violation tests ⇒…
Date of creation
3/25/2022 5:00 AM
|
|
Example 1: Max-margin classifier Example 2: Detecting star-shaped polygons Linear programming definition Geometric interpretation: Lowest point in a convex polyhedron Geometric structure and the…
Date of creation
3/23/2022 5:00 AM
|
|
four-way equivalence, via duality and lifting: Delaunay, Voronoi, lower hulls, and upper envelopes weighted Voronoi (power) diagrams and weighted Delaunay (coherent) triangulations tweaking Delaunay…
Date of creation
3/9/2022 6:00 AM
|
|
Randomized incremental algorithm outline Adding a safe bounding triangle: handling symbolic infinite coordinates History dag construction, O(n) expected size Analyzing expected time for all point…
Date of creation
3/4/2022 6:00 AM
|
|
local Delaunay condition and Lawson's flip algorithm paraboloid lifting map: locally Delaunay = locally convex lift locally Delaunay everywhere = locally convex lift everywhere = convex lift =…
Date of creation
3/2/2022 6:00 AM
|
|
Voronoi diagram definition Simple examples (2 or 3 points) Delaunay triangulation definition How to think/program about circles The incircle test Lawson's flip algorithm
Date of creation
2/25/2022 6:00 AM
|
|
Intuition: Tracing the polygon can be faster than using the history dag Crossing Lemma: E[#crossings] ≤ 4(n–r) Seidel's algorithm: Alternate between randomized incremental (using…
|
|
Review of insertion algorithm: expected time = O(1) plus point location Conflict lists: Every trapezoid knows which points it contains Backward analysis: O(n log n) expected time Special case:…
|
|
Duality in more detail: head*=left, tail*=right, clockwise*=counterclockwise Deletion* = contraction; Euler's formula by induction Inserting one segment into a trapezoidal decomposition Backward…
Date of creation
2/16/2022 6:00 AM
|
|
Gauss's point-in-polygon test Winding numbers Polygon area (Meister's shoelace algorithm)
Video credits
Jeff Erickson Contributors and team members
Jeff Erickson
|
|
Incidence lists for abstract (multi-)graphs Ordered incidence lists for planar maps, aka double-connected edge list Navigating DCELs Planar map duality (yet another pair of glasses) Euler's…
Date of creation
2/11/2022 6:00 AM
|