Videos and podcasts...
Here: you can find all videos available on Youtube for this course
All the videos of the course are on youtube: this will prevent saturation
hosting UCLouvain websites: everything is on
following channel containing all podcasts of Vincent Legat :-) or
following channel containing all podcasts of Jean-François Remacle :-) .
To watch the video on youtube, just
click on it. And do not forget to like the videos if you want us to continue to do them!
In those podcasts, Jean-François essentially convered 2 algorithms to compute convex hulls in 2D
- Jarvis's march which is in O(h n)
- Graham's scan which is in O(n log n)
There exist a better algorithm that is based on a divide and conquer approach
- Points are arbitrarily partitioned into m subsets of size p = n/m.
- Each subsets's convex hull is computed in (p log p) time using Graham Scan.
- Sub convex hulls are merged using a variation of a Jarvis march.
This algorithm is called Chan's algorithm : it is in n log (h) !!
It is well documented in wikipedia and in
the original paper.
For the students that choose convex hulls for their project, extending the two basic algorithms to Chan's method
is considered very positively :-)
Some source C++ files extracted from Gmsh's source code
www.gmsh.info so many things are
useless for your use. Anyway, functions that are useful have their signature in
