Search for tag: "computational geometry"

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 14 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 21 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 6 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 16 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 12 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 18 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 18 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 17 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 15 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 22 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 20 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 21 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 13 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 14 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 25 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 10 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 14 plays 0  

Feb 09: Elementary polygon algorithms

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

From  Jeff Erickson 23 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 23 plays 0  

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

From  Jeff Erickson 37 plays 0  

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…

From  Jeff Erickson 26 plays 0  

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…

From  Jeff Erickson 40 plays 0  

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…

From  Jeff Erickson 30 plays 0  

Jan 21: Graham's scan and Chan's algorithm

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 merge in O(n log h) time.

From  Jeff Erickson 81 plays 0