L11 - Convex Hull: Jarvis March Flashcards

1
Q

What makes a set of points convex?

A

A set S is convex if for any 2 points P,Q within S, all points along line PQ are in S.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Define a Convex Hull for a set of points

A

The convex hull of S is the smallest set of points that enclose all other points.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Give 3 examples of convex hull applications

A

Team formation analysis, collision detection, contamination zones

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Define the task specification for the Jarvis March algorithm (Problem, input, output, input-output relation)

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Explain how the Jarvis March algorithm works

A
  1. Establish orientation tournament based on smallest clockwise angle from the starting (left most) point.
  2. Add smallest point to convex hull set
  3. repeat tournament from this point
  4. Continue until all points are encountered.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the criterion for point selection in Jarvis March?

A

The point selected will be the one with the smallest clockwise right angle from the current point

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the worst case time complexity of Jarvis March? Give proof

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

In terms of Jarvis March applications, what is Onion Peeling? Give an example of it in use…

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What does the complexity of the algorithm depend on? What is the term for this?

A

Output sensitive - The complexity depends on the size of the output.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

In what scenarios is Jarvis March more efficient than Grahams Scan?

A

When the number of hull points is less than log N, where N is the input set of points.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly