-
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…
Apr 22: Visibility graphs
From Jeff Erickson
94 plays 0 -
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…
Apr 20: Fréchet distance continued
From Jeff Erickson
53 plays 0 -
Convolution A*B definition Minkowski sum A+B = points where A*B has positive winding number Fréchet distance definition (minimum leash length) Discrete…
Apr 15: Convolutions and Fréchet distance
From Jeff Erickson
47 plays 0 -
The translational motion planning problem Work space, configuration space, and free space Minkowski sum definition and naive construction Example with complexity…
Apr 13: Minkowski sums and motion planning
From Jeff Erickson
62 plays 0 -
Definitions: Shortest paths in polygons Rubber-band structure Incremental improvement Crossing structure The funnel algorithm Variant: Given crossing sequence instead of…
Apr 8: Geometric shortest paths
From Jeff Erickson
48 plays 0 -
Halfplane discrepancy Ham sandwich cuts Minimum-area triangles and affine degeneracy 3SUM and 3SUM-hardness
Apr 6: Applications of line arrangements
From Jeff Erickson
46 plays 0 -
Definitions Motivation Incremental algorithm: For each line, trace the zone in the arrangement of earlier lines The Zone Theorem
Apr 1: Line arrangements
From Jeff Erickson
50 plays 0 -
Smallest enclosing annulus: reduce to LP by linearization Smallest enclosing ball: Can't be linearized! Welzl's MinDisk algorithm Proof of solution uniqueness…
Mar 30: Generalizations of linear programming
From Jeff Erickson
45 plays 0 -
Set up and assumptions Seidel's incremental LP algorithm Proof of the exchange lemma Worst-case analysis of violation tests and basis computations Randomized…
Mar 25: Seidel's linear programming algorithm
From Jeff Erickson
148 plays 0 -
Example 1: Max-margin classifier Example 2: Detecting star-shaped polygons Linear programming definition Geometric interpretation: Lowest point in a convex polyhedron…
Mar 23: Linear programming intro
From Jeff Erickson
70 plays 0 -
four-way equivalence, via duality and lifting: Delaunay, Voronoi, lower hulls, and upper envelopes weighted Voronoi (power) diagrams and weighted Delaunay (coherent)…
Mar 09: Generalizations of Voronoi diagrams
From Jeff Erickson
48 plays 0 -
Randomized incremental algorithm outline Adding a safe bounding triangle: handling symbolic infinite coordinates History dag construction, O(n) expected size Analyzing…
Mar 04: Randomized incremental Delaunay…
From Jeff Erickson
65 plays 0 -
local Delaunay condition and Lawson's flip algorithm paraboloid lifting map: locally Delaunay = locally convex lift locally Delaunay everywhere = locally convex…
Mar 02: Delaunay triangulation proofs
From Jeff Erickson
65 plays 0 -
Voronoi diagram definition Simple examples (2 or 3 points) Delaunay triangulation definition How to think/program about circles The incircle test Lawson's flip…
Feb 25: Voronoi diagrams and Delaunay…
From Jeff Erickson
110 plays 0 -
Intuition: Tracing the polygon can be faster than using the history dag Crossing Lemma: E[#crossings] ≤ 4(n–r) Seidel's algorithm: Alternate between…
Feb 23: Faster polygon triangulation
From Jeff Erickson
43 plays 0 -
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)…
Feb 18: Randomized Incremental Construction II
From Jeff Erickson
37 plays 0 -
Duality in more detail: head*=left, tail*=right, clockwise*=counterclockwise Deletion* = contraction; Euler's formula by induction Inserting one segment into a…
Feb 16: Duality, Randomized Incremental…
From Jeff Erickson
49 plays 0 -
Gauss's point-in-polygon test Winding numbers Polygon area (Meister's shoelace algorithm)
Feb 09: Elementary polygon algorithms
From Jeff Erickson
72 plays 0 -
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…
Feb 11: Planar straight-line graphs
From Jeff Erickson
55 plays 0 -
Definitions: simple polygon, triangulation Look, it's the Jordan Curve Theorem! [Bolzano 184x, Jordan 1887] Jordan polygon theorem and the triangulation theorem…
Feb 04: Polygon triangulation
From Jeff Erickson
112 plays 0 -
Too much snow; we're remote again. Intersecting pairs ≥ intersection points Bentley-Ottman implicitly perturbs coincident intersections alart, but not…
Feb 02: Building a segment arrangement
From Jeff Erickson
66 plays 0 -
HDMI problems (sorry) Different formulations: Detection, counting, construction Two segments Sweep-line algorithm: Maintain a balanced BST of intersections with a…
Jan 28: Segment intersection
From Jeff Erickson
113 plays 0 -
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)…
Jan 25: Halfplane intersection
From Jeff Erickson
110 plays 0 -
More on 2d convex hulls Jarvis march review: O(nh) time Graham's scan: sort and repair in O(n log n) time Chan's algorithm: Shatter, compute subset hulls, and…
Jan 21: Graham's scan and Chan's…
From Jeff Erickson
496 plays 0
Search for ""