Search for tag: "computational geometry"
Feb 17: Straight-line Planar MapsStraight-line planar embedding, star-shaped-hole filling, canonical ordering, Schnyder woods, grid embedding
From Jeff Erickson
14 plays
0
|
|
Apr 22: Visibility graphsVisibility 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
78 plays
0
|
|
Apr 20: Fréchet distance continuedDecision 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 distanceConvolution 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
38 plays
0
|
|
Apr 13: Minkowski sums and motion planningThe 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
47 plays
0
|
|
Apr 8: Geometric shortest pathsDefinitions: 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
40 plays
0
|
|
Apr 6: Applications of line arrangementsHalfplane discrepancy Ham sandwich cuts Minimum-area triangles and affine degeneracy 3SUM and 3SUM-hardness
From Jeff Erickson
34 plays
0
|
|
Apr 1: Line arrangementsDefinitions Motivation Incremental algorithm: For each line, trace the zone in the arrangement of earlier lines The Zone Theorem
From Jeff Erickson
46 plays
0
|
|
Mar 30: Generalizations of linear programmingSmallest 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
42 plays
0
|
|
Mar 25: Seidel's linear programming algorithmSet 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
120 plays
0
|
|
Mar 23: Linear programming introExample 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
63 plays
0
|
|
Mar 09: Generalizations of Voronoi diagramsfour-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
40 plays
0
|
|
Mar 04: Randomized incremental Delaunay triangulationsRandomized 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
58 plays
0
|
|
Mar 02: Delaunay triangulation proofslocal 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
56 plays
0
|
|
Feb 25: Voronoi diagrams and Delaunay triangulationsVoronoi 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
101 plays
0
|
|
Feb 23: Faster polygon triangulationIntuition: 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
38 plays
0
|
|
Feb 18: Randomized Incremental Construction IIReview 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 ConstructionDuality 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
43 plays
0
|
|
Feb 09: Elementary polygon algorithmsGauss's point-in-polygon test Winding numbers Polygon area (Meister's shoelace algorithm)
From Jeff Erickson
63 plays
0
|
|
Feb 11: Planar straight-line graphsIncidence 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
|
|
Feb 04: Polygon triangulationDefinitions: 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,…
From Jeff Erickson
105 plays
0
|
|
Feb 02: Building a segment arrangementToo much snow; we're remote again. Intersecting pairs ≥ intersection points Bentley-Ottman implicitly perturbs coincident intersections alart, but not necessarily in a geometrically…
From Jeff Erickson
58 plays
0
|
|
Jan 28: Segment intersectionHDMI problems (sorry) Different formulations: Detection, counting, construction Two segments Sweep-line algorithm: Maintain a balanced BST of intersections with a vertical line Counting: Also…
From Jeff Erickson
105 plays
0
|
|
Jan 25: Halfplane intersectionImplementing 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…
From Jeff Erickson
88 plays
0
|