600.488 Homework Assignment 2

1. 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 algorithm without increasing the asymptotic running time.
2. 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 if you were aiming for O(n²) worst-case running time on any sequence of n insertions? O(n log n) worst-case running time?
3. Describe the details for implementing the randomized incremental construction algorithm for constructing the convex hull of n points in the plane. Specifically, say how conflicts are maintained and updated.
4. Say that a point p dominates 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.
5. 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).

Goodrich's Home Page.