Search for tag: "computational geometry"

48 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 12 plays 0 Date of creation 2/17/2023 12:00 AM
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 70 plays 0 Date of creation 4/22/2022 12: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 46 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 32 plays 0 Date of creation 4/15/2022 12: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 40 plays 0 Date of creation 4/13/2022 12: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 38 plays 0 Date of creation 4/8/2022 12: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 33 plays 0 Date of creation 4/6/2022 12: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 42 plays 0 Date of creation 4/1/2022 12: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 41 plays 0 Date of creation 3/30/2022 12: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 90 plays 0 Date of creation 3/25/2022 12: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 55 plays 0 Date of creation 3/23/2022 12: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 38 plays 0 Date of creation 3/9/2022 12: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 55 plays 0 Date of creation 3/4/2022 12: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 55 plays 0 Date of creation 3/2/2022 12: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 91 plays 0 Date of creation 2/25/2022 12: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 37 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 42 plays 0 Date of creation 2/16/2022 12: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 60 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 12:00 AM
Feb 04: Polygon triangulation duration 1 hour 16 minutes Feb 04: Polygon triangulation Feb 04: Polygon triangulation	Feb 04: Polygon triangulation Definitions: simple polygon, triangulation Look, it's the Jordan Curve Theorem! [Bolzano 184x, Jordan 1887] Jordan polygon theorem and the triangulation theorem [Schönflies 1896, Dehn 1899,… computational geometry From Jeff Erickson 103 plays 0 Date of creation 2/4/2022 12:00 AM
Feb 02: Building a segment arrangement duration 1 hour 11 minutes Feb 02: Building a segment arrangement Feb 02: Building a segment arrangement	Feb 02: Building a segment arrangement Too much snow; we're remote again. Intersecting pairs ≥ intersection points Bentley-Ottman implicitly perturbs coincident intersections alart, but not necessarily in a geometrically… computational geometry From Jeff Erickson 51 plays 0 Date of creation 2/2/2022 12:00 AM
Jan 28: Segment intersection duration 1 hour 11 minutes Jan 28: Segment intersection Jan 28: Segment intersection	Jan 28: Segment intersection HDMI problems (sorry) Different formulations: Detection, counting, construction Two segments Sweep-line algorithm: Maintain a balanced BST of intersections with a vertical line Counting: Also… computational geometry From Jeff Erickson 100 plays 0 Date of creation 1/26/2022 12:00 AM
Jan 25: Halfplane intersection duration 1 hour 16 minutes Jan 25: Halfplane intersection Jan 25: Halfplane intersection	Jan 25: Halfplane intersection Implementing Chan's little birdie (doubly-exponential search) The upper envelope problem Merge-envelope: Split into two subsets, recurse, and merge in O(n log n) time. Merging via sweep-line… computational geometry From Jeff Erickson 81 plays 0 Date of creation 1/26/2022 12: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