Search for tag: "geometry"

64 Media

Feb 17: Straight-line Planar Maps duration 1 hour 14 minutes Feb 17: Straight-line Planar Maps Feb 17: Straight-line Planar Maps	Feb 17: Straight-line Planar Maps Straight-line planar embedding, star-shaped-hole filling, canonical ordering, Schnyder woods, grid embedding computational geometry From Jeff Erickson 15 plays 0 Date of creation 2/17/2023 6:00 AM
Toby Stafford, Invariant holonomic systems for… duration 56 minutes 26 seconds Toby Stafford, Invariant holonomic systems for… Toby Stafford, Invariant holonomic systems for symmetric spaces	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. equivariant eigendistributions +3 More From Shelby Koehne 10 plays 0 Date of creation 6/12/2022 5:00 AM Video credits Jennifer Nygard
Travis Schedler, D-modules and rings of… duration 1 hour 0 minutes Travis Schedler, D-modules and rings of… Travis Schedler, D-modules and rings of differential operators in singular and noncommutative settings	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. d-modules +3 More From Shelby Koehne 28 plays 0 Date of creation 6/12/2022 5:00 AM Video credits Jennifer Nygard
Susan Sierra, Blowing down noncommutative cubic… duration 1 hour 7 minutes Susan Sierra, Blowing down noncommutative cubic… Susan Sierra, Blowing down noncommutative cubic surfaces	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. cubic surfaces +3 More From Shelby Koehne 21 plays 0 Date of creation 6/11/2022 5:00 AM Video credits Jennifer Nygard
Gwyn Bellamy, Birational geometry of quiver… duration 59 minutes 23 seconds Gwyn Bellamy, Birational geometry of quiver… Gwyn Bellamy, Birational geometry of quiver varieties	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. birational geometry +4 More From Shelby Koehne 26 plays 0 Date of creation 6/11/2022 5:00 AM Video credits Jennifer Nygard
Apr 22: Visibility graphs duration 1 hour 13 minutes Apr 22: Visibility graphs Apr 22: Visibility graphs	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:… computational geometry From Jeff Erickson 78 plays 0 Date of creation 4/22/2022 5:00 AM
Apr 20: Fréchet distance continued duration 1 hour 18 minutes Apr 20: Fréchet distance continued Apr 20: Fréchet distance continued	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… computational geometry From Jeff Erickson 47 plays 0
Apr 15: Convolutions and Fréchet distance duration 1 hour 15 minutes Apr 15: Convolutions and Fréchet distance Apr 15: Convolutions and Fréchet distance	Apr 15: Convolutions and Fréchet distance Convolution AB definition Minkowski sum A+B = points where AB has positive winding number Fréchet distance definition (minimum leash length) Discrete Fréchet distance via dynamic… computational geometry From Jeff Erickson 39 plays 0 Date of creation 4/15/2022 5:00 AM
Apr 13: Minkowski sums and motion planning duration 1 hour 13 minutes Apr 13: Minkowski sums and motion planning Apr 13: Minkowski sums and motion planning	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 =… computational geometry From Jeff Erickson 50 plays 0 Date of creation 4/13/2022 5:00 AM
Apr 8: Geometric shortest paths duration 1 hour 11 minutes Apr 8: Geometric shortest paths Apr 8: Geometric shortest paths	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 … computational geometry From Jeff Erickson 40 plays 0 Date of creation 4/8/2022 5:00 AM
Apr 6: Applications of line arrangements duration 1 hour 19 minutes Apr 6: Applications of line arrangements Apr 6: Applications of line arrangements	Apr 6: Applications of line arrangements Halfplane discrepancy Ham sandwich cuts Minimum-area triangles and affine degeneracy 3SUM and 3SUM-hardness computational geometry From Jeff Erickson 34 plays 0 Date of creation 4/6/2022 5:00 AM
Apr 1: Line arrangements duration 1 hour 14 minutes Apr 1: Line arrangements Apr 1: Line arrangements	Apr 1: Line arrangements Definitions Motivation Incremental algorithm: For each line, trace the zone in the arrangement of earlier lines The Zone Theorem computational geometry From Jeff Erickson 46 plays 0 Date of creation 4/1/2022 5:00 AM
Mar 30: Generalizations of linear programming duration 1 hour 16 minutes Mar 30: Generalizations of linear programming Mar 30: Generalizations of linear programming	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… computational geometry From Jeff Erickson 42 plays 0 Date of creation 3/30/2022 5:00 AM
Mar 25: Seidel's linear programming algorithm duration 1 hour 16 minutes Mar 25: Seidel's linear programming algorithm Mar 25: Seidel's linear programming algorithm	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 ⇒… computational geometry From Jeff Erickson 130 plays 0 Date of creation 3/25/2022 5:00 AM
Mar 23: Linear programming intro duration 1 hour 13 minutes Mar 23: Linear programming intro Mar 23: Linear programming intro	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… computational geometry From Jeff Erickson 63 plays 0 Date of creation 3/23/2022 5:00 AM
Mar 09: Generalizations of Voronoi diagrams duration 58 minutes 18 seconds Mar 09: Generalizations of Voronoi diagrams Mar 09: Generalizations of Voronoi diagrams	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… computational geometry From Jeff Erickson 41 plays 0 Date of creation 3/9/2022 6:00 AM
Mar 04: Randomized incremental Delaunay… duration 1 hour 13 minutes Mar 04: Randomized incremental Delaunay… Mar 04: Randomized incremental Delaunay triangulations	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… computational geometry From Jeff Erickson 58 plays 0 Date of creation 3/4/2022 6:00 AM
Mar 02: Delaunay triangulation proofs duration 1 hour 14 minutes Mar 02: Delaunay triangulation proofs Mar 02: Delaunay triangulation proofs	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 =… computational geometry From Jeff Erickson 57 plays 0 Date of creation 3/2/2022 6:00 AM
Feb 25: Voronoi diagrams and Delaunay… duration 1 hour 15 minutes Feb 25: Voronoi diagrams and Delaunay… Feb 25: Voronoi diagrams and Delaunay triangulations	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 computational geometry From Jeff Erickson 101 plays 0 Date of creation 2/25/2022 6:00 AM
Feb 23: Faster polygon triangulation duration 1 hour 13 minutes Feb 23: Faster polygon triangulation Feb 23: Faster polygon triangulation	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… computational geometry From Jeff Erickson 38 plays 0
Feb 18: Randomized Incremental Construction II duration 1 hour 17 minutes Feb 18: Randomized Incremental Construction II Feb 18: Randomized Incremental Construction II	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:… computational geometry From Jeff Erickson 32 plays 0
Feb 16: Duality, Randomized Incremental… duration 1 hour 15 minutes Feb 16: Duality, Randomized Incremental… Feb 16: Duality, Randomized Incremental Construction	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… computational geometry From Jeff Erickson 43 plays 0 Date of creation 2/16/2022 6:00 AM
Feb 09: Elementary polygon algorithms duration 1 hour 12 minutes Feb 09: Elementary polygon algorithms Feb 09: Elementary polygon algorithms	Feb 09: Elementary polygon algorithms Gauss's point-in-polygon test Winding numbers Polygon area (Meister's shoelace algorithm) computational geometry From Jeff Erickson 64 plays 0 Video credits Jeff Erickson Contributors and team members Jeff Erickson
Feb 11: Planar straight-line graphs duration 1 hour 11 minutes Feb 11: Planar straight-line graphs Feb 11: Planar straight-line graphs	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… computational geometry From Jeff Erickson 52 plays 0 Date of creation 2/11/2022 6:00 AM

	Contact Technology Services to report an issue, offer feedback, or request assistance.
	Technology Services Home \| Kaltura Help \| Privacy Policy
	Illinois Media Space, © 2022 Board of Trustees of the University of Illinois