Java Reference
In-Depth Information
Step 3: Push p
0
, p
1
, and p
2
into stack
H
. (After the algorithm finishes,
H contains all the points in the convex hull.)
Step 4:
i = 3;
while (i < n) {
Let t
1
and t
2
be the top first and second element in stack
H
;
if (p
i
is on the left side of the direct line from t
2
to t
1
) {
Push p
i
to H;
i++; // Consider the next point in
S
.
}
else
Pop the top element off stack
H
.
}
Step 5: The points in
H
form a convex hull.
The convex hull is discovered incrementally. Initially,
p
0
,
p
1
,and
p
2
form a convex hull.
Consider
p
3
.
p
3
is outside of the current convex hull since points are sorted in increasing order
of their angles. If
p
3
is strictly on the left side of the line from
p
1
to
p
2
(see Figure 22.10c),
push
p
3
into
H
. Now
p
0
,
p
1
,
p
2
, and
p
3
form a convex hull. If
p
3
is on the right side of the line
from
p
1
to
p
2
(see Figure 22.10d), pop
p
2
out of
H
and push
p
3
into
H
. Now
p
0
,
p
1
, and
p
3
form a convex hull and
p
2
is inside of this convex hull. You can prove by induction that all the
points in
H
in Step 5 form a convex hull for all the points in the input list
S
.
Finding the rightmost lowest point in Step 1 can be done in
O
(
n
) time. The angles can be
computed using trigonometry functions. However, you can sort the points without actually
computing their angles. Observe that
p
2
would make a greater angle than
p
1
if and only if
p
2
lies on the left side of the line from
p
0
to
p
1
. Whether a point is on the left side of a line can
be determined in
O
(1) time, as shown in Programming Exercise 3.32. Sorting in Step 2 can be
done in
O
(
n
log
n
) time using the merge-sort or heap-sort algorithms that will be introduced
in Chapter 23. Step 4 can be done in
O
(
n
) time. Therefore, the algorithm takes
O
(
n
log
n
) time.
The implementation of this algorithm is left as an exercise (see Programming Exercise 22.11).
correctness of the algorithm
time complexity of the
algorithm
22.24
✓
✓
What is a convex hull?
Check
22.25
Describe the gift-wrapping algorithm for finding a convex hull. Should list
H
be
implemented using an
ArrayList
or a
LinkedList
?
Point
22.26
Describe Graham's algorithm for finding a convex hull. Why does the algorithm use
a stack to store the points in a convex hull?
K
EY
T
ERMS
average-case analysis
822
dynamic programming approach
832
backtracking approach
846
exponential time
829
best-case input
822
growth rate 822
logarithmic time 828
quadratic time 825
space complexity
Big
O
notation
822
brute force 833
constant time 823
convex hull 849
divide-and-conquer approach
823
time complexity
823
844
worst-case input
822
C
HAPTER
S
UMMARY
1.
The
Big O notation
is a theoretical approach for analyzing the performance of an
algorithm. It estimates how fast an algorithm's execution time increases as the input
size increases, which enables you to compare two algorithms by examining their
growth rates
.
Search WWH ::
Custom Search