L11 - Convex Hull: Jarvis March Flashcards
What makes a set of points convex?
A set S is convex if for any 2 points P,Q within S, all points along line PQ are in S.
Define a Convex Hull for a set of points
The convex hull of S is the smallest set of points that enclose all other points.
Give 3 examples of convex hull applications
Team formation analysis, collision detection, contamination zones
Define the task specification for the Jarvis March algorithm (Problem, input, output, input-output relation)
Problem: Establish the smallest set of points that enclose all other points
Input: is a set of points
Output: is the convex hull set of points in clockwise order
Input-output: relation is that output contains the convex hull set H from the original input set S.
Explain how the Jarvis March algorithm works
- Establish orientation tournament based on smallest clockwise angle from the starting (left most) point.
- Add smallest point to convex hull set
- repeat tournament from this point
- Continue until all points are encountered.
What is the criterion for point selection in Jarvis March?
The point selected will be the one with the smallest clockwise right angle from the current point
What is the worst case time complexity of Jarvis March? Give proof
O(HN) where H is the set of hull points and N is the set of all points.
This is because for each hull point, N-K points need to be searched to establish the next point to move to.
In terms of Jarvis March applications, what is Onion Peeling? Give an example of it in use…
Onion Peeling the process of iteratively establishing the convex hull within convex hulls until a central point is identified.
An example of this in use is to find an animal habitat within a vast region.
What does the complexity of the algorithm depend on? What is the term for this?
Output sensitive - The complexity depends on the size of the output.
In what scenarios is Jarvis March more efficient than Grahams Scan?
When the number of hull points is less than log N, where N is the input set of points.