Search for tag: "geometry"

Feb 17: Straight-line Planar Maps

Straight-line planar embedding, star-shaped-hole filling, canonical ordering, Schnyder woods, grid embedding

From  Jeff Erickson 12 plays 0  

Toby Stafford, Invariant holonomic systems for symmetric spaces

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.

From  Shelby Koehne 10 plays 0  

Travis Schedler, D-modules and rings of differential operators in singular and noncommutative settings

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.

From  Shelby Koehne 20 plays 0  

Susan Sierra, Blowing down noncommutative cubic surfaces

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.

From  Shelby Koehne 20 plays 0  

Gwyn Bellamy, Birational geometry of quiver varieties

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.

From  Shelby Koehne 26 plays 0  

Apr 22: Visibility graphs

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:…

From  Jeff Erickson 72 plays 0  

Apr 20: Fréchet distance continued

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…

From  Jeff Erickson 46 plays 0  

Apr 15: Convolutions and Fréchet distance

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…

From  Jeff Erickson 32 plays 0  

Apr 13: Minkowski sums and motion planning

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 =…

From  Jeff Erickson 40 plays 0  

Apr 8: Geometric shortest paths

Definitions: Shortest paths in polygons Rubber-band structure Incremental improvement Crossing structure The funnel algorithm Variant: Given crossing sequence instead of explicit coordinates …

From  Jeff Erickson 38 plays 0  

Apr 6: Applications of line arrangements

Halfplane discrepancy Ham sandwich cuts Minimum-area triangles and affine degeneracy 3SUM and 3SUM-hardness

From  Jeff Erickson 33 plays 0  

Apr 1: Line arrangements

Definitions Motivation Incremental algorithm: For each line, trace the zone in the arrangement of earlier lines The Zone Theorem

From  Jeff Erickson 42 plays 0  

Mar 30: Generalizations of linear programming

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…

From  Jeff Erickson 41 plays 0  

Mar 25: Seidel's linear programming algorithm

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 ⇒…

From  Jeff Erickson 92 plays 0  

Mar 23: Linear programming intro

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…

From  Jeff Erickson 55 plays 0  

Mar 09: Generalizations of Voronoi diagrams

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…

From  Jeff Erickson 38 plays 0  

Mar 04: Randomized incremental Delaunay triangulations

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…

From  Jeff Erickson 56 plays 0  

Mar 02: Delaunay triangulation proofs

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 =…

From  Jeff Erickson 55 plays 0  

Feb 25: Voronoi diagrams and Delaunay triangulations

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

From  Jeff Erickson 93 plays 0  

Feb 23: Faster polygon triangulation

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…

From  Jeff Erickson 37 plays 0  

Feb 18: Randomized Incremental Construction II

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:…

From  Jeff Erickson 32 plays 0  

Feb 16: Duality, Randomized Incremental Construction

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…

From  Jeff Erickson 42 plays 0  

Feb 09: Elementary polygon algorithms

Gauss's point-in-polygon test Winding numbers Polygon area (Meister's shoelace algorithm)

From  Jeff Erickson 62 plays 0  

Feb 11: Planar straight-line graphs

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…

From  Jeff Erickson 52 plays 0