-
From Jeff Erickson
70 plays 0Visibility 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… -
From Jeff Erickson
46 plays 0Decision 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… -
From Jeff Erickson
31 plays 0Convolution A*B definition Minkowski sum A+B = points where A*B has positive winding number Fréchet distance definition (minimum leash length) Discrete… -
From Jeff Erickson
40 plays 0The translational motion planning problem Work space, configuration space, and free space Minkowski sum definition and naive construction Example with complexity… -
From Jeff Erickson
38 plays 0Definitions: Shortest paths in polygons Rubber-band structure Incremental improvement Crossing structure The funnel algorithm Variant: Given crossing sequence instead of… -
From Jeff Erickson
33 plays 0Halfplane discrepancy Ham sandwich cuts Minimum-area triangles and affine degeneracy 3SUM and 3SUM-hardness -
From Jeff Erickson
42 plays 0Definitions Motivation Incremental algorithm: For each line, trace the zone in the arrangement of earlier lines The Zone Theorem -
From Jeff Erickson
41 plays 0Smallest enclosing annulus: reduce to LP by linearization Smallest enclosing ball: Can't be linearized! Welzl's MinDisk algorithm Proof of solution uniqueness… -
From Jeff Erickson
90 plays 0Set up and assumptions Seidel's incremental LP algorithm Proof of the exchange lemma Worst-case analysis of violation tests and basis computations Randomized… -
From Jeff Erickson
55 plays 0Example 1: Max-margin classifier Example 2: Detecting star-shaped polygons Linear programming definition Geometric interpretation: Lowest point in a convex polyhedron… -
From Jeff Erickson
38 plays 0four-way equivalence, via duality and lifting: Delaunay, Voronoi, lower hulls, and upper envelopes weighted Voronoi (power) diagrams and weighted Delaunay (coherent)… -
From Jeff Erickson
55 plays 0Randomized incremental algorithm outline Adding a safe bounding triangle: handling symbolic infinite coordinates History dag construction, O(n) expected size Analyzing… -
From Jeff Erickson
55 plays 0local Delaunay condition and Lawson's flip algorithm paraboloid lifting map: locally Delaunay = locally convex lift locally Delaunay everywhere = locally convex… -
From Jeff Erickson
91 plays 0Voronoi diagram definition Simple examples (2 or 3 points) Delaunay triangulation definition How to think/program about circles The incircle test Lawson's flip… -
From Jeff Erickson
37 plays 0Intuition: Tracing the polygon can be faster than using the history dag Crossing Lemma: E[#crossings] ≤ 4(n–r) Seidel's algorithm: Alternate between… -
From Jeff Erickson
30 plays 0Review 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)… -
From Jeff Erickson
39 plays 0Duality in more detail: head*=left, tail*=right, clockwise*=counterclockwise Deletion* = contraction; Euler's formula by induction Inserting one segment into a… -
From Jeff Erickson
59 plays 0Gauss's point-in-polygon test Winding numbers Polygon area (Meister's shoelace algorithm) -
From Jeff Erickson
52 plays 0Incidence lists for abstract (multi-)graphs Ordered incidence lists for planar maps, aka double-connected edge list Navigating DCELs Planar map duality (yet another pair… -
From Jeff Erickson
103 plays 0Definitions: simple polygon, triangulation Look, it's the Jordan Curve Theorem! [Bolzano 184x, Jordan 1887] Jordan polygon theorem and the triangulation theorem… -
From Jeff Erickson
51 plays 0Too much snow; we're remote again. Intersecting pairs ≥ intersection points Bentley-Ottman implicitly perturbs coincident intersections alart, but not… -
From Jeff Erickson
99 plays 0HDMI problems (sorry) Different formulations: Detection, counting, construction Two segments Sweep-line algorithm: Maintain a balanced BST of intersections with a… -
From Jeff Erickson
79 plays 0Implementing 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)… -
From Jeff Erickson
401 plays 0More 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…
Skip to content
- Home
- Public Affairs
- About Illinois
-
Colleges
-
ACES
- ACES Technology Services
- Agricultural and Biological Engineering
- Agricultural and Consumer Economics
- Agricultural Communications
- Agricultural Education
- Animal Sciences
- Career Services
- Crop Sciences
- Division of Nutritional Sciences
- Food Science and Human Nutrition
- Human Development and Family Studies
- Natural Resources and Environmental Sciences
- Applied Health Sciences
- Carle Illinois College of Medicine
- College of Media
- Education
- Fine & Applied Arts
- General Studies
- Gies College of Business
- Graduate College
- Grainger Engineering
- Labor & Employment Relations
- Law
-
Liberal Arts & Sciences
- ATLAS
- Center for East Asian and Pacific Studies
- Center for Latin American and Caribbean Studies
- Chemistry
- French and Italian
- GGIS
- Jewish Studies
- LAS International Programs
- LAS Teaching Academy
- Math
- MCB Advising Program
- Program in Jewish Culture and Society
- Slavic Languages and Literature
- Sociology
- Sociology Advising
- School of Information Sciences
- Social Work
- Veterinary Medicine
-
ACES
- Research
- Student Life
- Campus Units
- Channels
- Help
- Home
- Public Affairs
- About Illinois
-
Colleges
-
ACES
- ACES Technology Services
- Agricultural and Biological Engineering
- Agricultural and Consumer Economics
- Agricultural Communications
- Agricultural Education
- Animal Sciences
- Career Services
- Crop Sciences
- Division of Nutritional Sciences
- Food Science and Human Nutrition
- Human Development and Family Studies
- Natural Resources and Environmental Sciences
- Applied Health Sciences
- Carle Illinois College of Medicine
- College of Media
- Education
- Fine & Applied Arts
- General Studies
- Gies College of Business
- Graduate College
- Grainger Engineering
- Labor & Employment Relations
- Law
-
Liberal Arts & Sciences
- ATLAS
- Center for East Asian and Pacific Studies
- Center for Latin American and Caribbean Studies
- Chemistry
- French and Italian
- GGIS
- Jewish Studies
- LAS International Programs
- LAS Teaching Academy
- Math
- MCB Advising Program
- Program in Jewish Culture and Society
- Slavic Languages and Literature
- Sociology
- Sociology Advising
- School of Information Sciences
- Social Work
- Veterinary Medicine
-
ACES
- Research
- Student Life
- Campus Units
- Channels
- Help
Spring 2022 lectures for CS 498 TC: Computational Geometry, taught by Jeff Erickson
…Read more
Less…