Assume that P is a closed polyline
in which no three consecutive vertices lie on the same line. The
following linear-time algorithm to check if P is the boundary of a convex
polygon does not work:
If every consecutive sequence of three vertices along P form a left-turn,
then say that P is convex. Otherwise, say that P is not convex.
Draw an example polyline which the algorithm incorrectly
decides is the boundary of a convex polygon.
Fix the previous algorithm without increasing its asymptotic running time.
Describe an incremental algorithm to maintain the convex
hull of a set of points
as points are inserted on-line, that is, you do not know the list of
points in advance (and we do not allow point removal).
What data structures would you use to maintain the hull
if you were aiming for
O(n^{2})
worst-case running time on any sequence of n insertions?
O(n log n) worst-case
running time?
Say that a point pdominates a point q if the x-
and y-coordinates of p are both greater than the respective x-
and y-coordinates of q.
Given a set S of n points in the plane, describe
an O(n log n) time algorithm for finding every
point in S that is not dominated by any other point in
S.
Given a convex polygon P whose vertices are stored in an
array, describe an O(log n) time algorithm for finding
the two intersection points between a line L and the boundary
of P (if such points exist).