Convex Hull Algorithms

Показать описание

This video is about algorithms for computing the convex hull of points in 2D. Specifically, we consider the following algorithms:
- a slow (cubic-time) algorithm,
- Graham scan (O(n log n) time),
- the giftwrapping algorithm (O(n*h) time, where h is the number of points on the hull), and
- Chan's algorithm (O(n log h) time).

Next to talking about convex hull algorithms, this video also serves as a first introduction to geometric algorithm design.

To interact with the notebook open it in Binder (the 3 rings at the top right corner).

00:00 introduction and definitions
03:28 the convex hull problem
07:15 designing geometric algorithms
09:43 slow algorithm
11:57 Graham scan
16:48 Graham scan: correctness
18:17 Graham scan: running time analysis
24:34 giftwrapping algorithm
26:54 giftwrapping: correctness
29:00 Chan's algorithm
37:05 Summary and Discussion

Algorithms Lab

Рекомендации по теме

Комментарии

Excellent video, really well explained, with clear examples. Thank you.

DanielWood

hey this is an emergency i need some kind of code for a problem like you have given points in a 2d space and you have to find the minimum number of points to make a structure that if the points freefall downwards then you can catch them in that structure that no point fall on ground

No_one_is_here

Im struggling to understand why m is limited to n since it does not seem to make a difference in functionality or (what I understood) runningtime.
(Same amount of partitions for m=n as for m>n and the algorithm terminates after finding at most n Hull points anyway)
Could you provide some example how m > n could bring drawbacks?

miauuuauLP

Given the CCW ordering of a simple polygon with N points, is possible to compute its convex hull in O(N)..

eddJomsAntony

While I was looking at the timings of Convex Hull computation times using the monoton chain algorithm on a lexicographically sorted integer points in an intel Xeon 2.40 GHz × 32 machine, I observed that for the time taken for 1000 points, 10000 and points are all very close, Is this OK?

jomsantony

for Graham scan we need to reverse the order of P and then compute the lower hull too right?

kokala

Are there applications where the input point set consists of millions of points. Will it be worth exploring GPU accelerated methods for finding the convex hull of such input sets

jomsantony

Given the convex hull of a set of points Is it possible to come up with its Delaunay triangulation with less than nlogn time

jomsantony

Convex Hull Algorithms

Convex Hull Algorithm - Graham Scan and Jarvis March tutorial

Convex Hull Algorithms

Gift Wrapping Algorithm (Convex Hull)

Convex hulls: Graham scan - Inside code

Convex Hull: Starting with graph algorithms for interviews

Convex hulls: Jarvis march algorithm (gift-wrapping) - Inside code

GRAHAM SCAN ALGORITHM | Convex Hull | (solved example)

Convex Hull Jarvis March(Gift wrapping algorithm)

Lesson 2 (BLOCK I) | Design and Analysis of Algorithms | MCS 211 | No.1 IGNOU Coaching App #ignou

Convex Hull | Basics | Lecture-1

2. Divide & Conquer: Convex Hull, Median Finding

Convex Hull Demo

Graham Scan Tutorial: Convex Hull of a Set of 2D Points

Convex hull animation (DFS, 10000 points, no search details)

convex hull algorithm (part 1)

Convex Hulls -- Graham Scan

Coding Challenge #148: Gift Wrapping Algorithm (Convex Hull)

Lecture 24: Convex Hull | Sorting Algorithms in Computational Geometry | Sorting for Convex Hull

BRUTE FORCE-CONVEX HULL

Convex Hull or Mixing Things (5/5) | Computational Geometry - Lecture 01

Convex Hull in 3D (1/5) | Computational Geometry - Lecture 09

Convex Hull - DC Algorithm - Divide & Conquer | Design & Analysis of Algorithms #daa #algori...

Final Project - Convex Hull Algorithms

The Quickhull Algorithm