600.488 Homework Assignment 2

by: Breno de Medeiros
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.


2) Fix the previous algorithm without increasing its asymptotic running time.

Solution: At each left-turn, compute by how much you have turned (the angle of turning).
If at any time the sum of all turning angles is larger than a full circular turn (360 degrees),
then the closed polyline does not represent a convex polygon.  Note that we have increased
a constant amount of work per step of the previous algorithm.

3) 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(n2) worst-case running time on any sequence of n insertions? O(n log n)
worst-case running time?

We store the points as entries in an ordered dictionary.  Each point entered will be assigned
a key,  which will either be the number -1 or a positive rational number.  Each positive key
is unique, but the key -1 will typically be shared by several points.  The number 0 is not a
valid key.

For example, the first three point gets assigned the keys 100, 200, 300.  The idea is that
points with positive keys belong to the boundary of the convex hull, and starting by the
point with lowest positive key, and browsing the dictionary by picking always the point
with next lowest key we traverse the boundary of the convex hull in order.  Points not in
the hull have key equal to -1.

Every time a new point is entered, a computation will be made that will determine whether
the point is in the boundary of the convex hull, and will assign this point a key.  Then the
pair (point, key) will be added to the dictionary.  If any of the points that belonged to
the boundary of the hull become interior points after the addition of the new point, they
have their keys updated to the value -1.

I will sketch the ideas of the algorithm.  Let be the hull of our set of points right before
we enter a point P. We assume H has at least three points, or the result is trivial.  We assume
we have a binary search method to find the vertex in  lying closest to P.  This is not
hard to implement, since our dictionary encodes the boundary of the convex hull in order.
Let  V'  and  V''  stand respectively, for the precursor and successor of  in  H.
The picture below show the possible positions for  P with respect to the corner at V.

If P is in the area marked as 1, then P is in the interior of the hull and should be inserted
with key = -1.  If P lies in the region marked 2, it should receive a key of intermediate
value between that of  V' and V.   Similarly,  on region 3, it receives a key of value
intermediate between that of  V and V''.  On region 4, it receives the same key as that
of  V, and the key of  V is set to -1.  In the cases 2, 3, 4, further adjustments
may be necessary.  I will assume the case P2, the other ones being similar.

If the new boundary consisting of H (maybe with V removed) and P has left turns V' and
V'', no adjustments need be made. If however, the turn at V' is a right turn, then use a
binary search method to find the first vertex W before V' such that connecting V' to P will
preserve a left turn at V'.  Then all vertices on H intermediate between W and P have their
keys adjusted to -1.  Do the same after P, with the vertex at V or V'', finding  Z.  After
these adjustments, we clearly have maintained the hull information.

Remark:  When we said assign an intermediate value for the key, a case comes to mind
when P lies between the vertex with lowest and highest key. (They are consecutive, since
the natural order of the problem is circular, while we have a linear order in the
dictionary.) Then just assign to P a key value larger than the highest key.

Now let's analyze the algorithm.  When a new point  P is entered, we must perform
at most three binary searches in order to find the vertices immediately preceding and
succeding P.  We may also change the keys of an unknown number of points to -1.  We
charge the time of key change to the particular points which had keys changed, since once
a point is assigned the key -1 it never again is accessed or participates on any search
(for all purposes, our dictionary is able only to list all points with key -1, (in arbitrary order)
but they will never be considered when one of the binary searches is performed.)
We then insert the pair consisting of P and its key.  So every vertex given triggers
binary searches, is inserted once and another time may have his key changed to -1, which
will force an update of the dictionary.  The running time of the whole algorithm is thus
O(nq), where q is the costliest (in terms of time) of each of the operations: search, insert,

If we implement our dictionary with a structure such that the costliest of this operations is
O(n) (such as any linear data strucuture, as a linked list, an array, etc.) then we get O(n^2)
worst case performance.  If on the other hand, we use a balanced search tree, which
implements all these operations in O(log(n)) time, then we get O(nlog(n)) worst case
running time.

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.

Solution:  We break the algorithm in steps.

Step1 (Initialize):  Sort the points by increasing x-coordinate, storing them in sequence S1.
Remove first point of S1 (minimum x-coordinate) and place it in another sequence S2.

Step2 (S1 empty?): If S1 is empty, return S2.

Step3 (Keep y- decreasing): If S2 is empty, remove P from S1, add it to S2 and loop back to
Step2. Else call P the first point in S1, Q the last point in S2. Compare their y-coordinates.
If the y-coordinate of P is less than that of Q, remove it from S1, add it to S2 and loop back to step2.  If, on the other hand, the y-coordinate of  P is bigger than that of Q, remove Q from S2
and loop back to Step3.

Analysis of time: Every time the loop consisting of  Steps 2 and 3 is executed, it either adds
a point to S2, or removes a point from it.  Every point in the original sequence S1 is added
once to S2, and removed at most once.  So the last two steps together contribute with O(n)
time.  Step 1 is a sorting procedure, executed in O(nlogn) optimally.

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).

Solution: Spelling out all the details of the algorithm will clutter the ideas.  I will give a
high-level description on how it should proceed.

Let PArray be the name of the array storing the points on the boundary of P, so that these
points can be retrieved by indexing PArray with any integer number k.  If that number is
not in the range 0,... n-1 then modular arithmetic is understood and PArray[k mod n] will
be returned.

By a section of PArray defined by two integers r and s we understand all points of the
form PArray[r], PArray[r+1], ..., PArray[s].  This is the case even in the case when s is
smaller than r, but now the section loops around the index 0.

Since the algorithm is required to run in logarithmic time, it is clear that the intersection
points will have to be found using binary search methods.  We will have a subroutine
called SPLIT_SEARCH that is called with two integer parameters, r and s.  The points
PArray[r] and PArray[s] will then lie on opposite sides of  L.  SPLIT_SEARCH then
checks whether the vertice "halfway" between r and s (more precisely, the vertex given
by t = r + abs(s-r)/2 ) lies on the same or opposite side of L from r.  In the first case,
SPLIT_SEARCH will recursively invoke itself on the section given by t and s, otherwise
on the one given by r and t.  When r and s are consective integers (in the modular sense)
then SPLIT_SEARCH  returns the intersection of the edge PArray[r]PArray[s] with L.

Of course, SPLIT_SEARCH will only be called upon when we have found two vertices
at opposite sides of L. We now need a binary search method for such a pair of points, if
indeed they exist.

FIND_OPPOSITE is the routine which finds a pair of opposite points, if they exist. It also
receives as a parameter a pair of r, s of integers. We now describe it.

FIND_OPPOSITE starts by checking whether PArray[r] and PArray[s] lie at opposite sides
of L.  In this case, it calls SPLIT_SEARCH on the two sections of PArray defined by r and  s.

If both points lie on the same side of L, Let Q be the closest to L, and W the furthest.  Let L' be
the line through Q parallel to L. Let Q' be the point preceding Q in PArray and Q''  the point following Q.

There are several cases to consider, according to the relative positions of L', Q' and Q''.

Case1: Both Q' and Q'' might lie between L and L', so closer to L than Q.  It is easier then to
verify that convexity implies now that the whole of P lies to the same side of L as Q'.
(The line L' is said in this case to support P at Q.) But that would then establish Q
as the furthest point in P to L, in obvious contradiction with the choice of Q.  So this case
will never occur.

Case2: Both Q' and Q'' lie in the side of L' away from L. In this case, all of P is on the side
of L' away from L and there are no points to be found.  FIND_OPPOSITE ends, indicating
that the intersection does not exist.

Case3: Only one of Q' and Q'' lies on the side of L' closer to L.  Without loss of generality,
assume this is Q'. Any intersection will happen in the section of the boundary between Q'
and W that does not contain Q.  We find Z the point halfway between W and Q'.  If Z is on
the opposite side of L from Q' we finish by calling SPLIT_SEARCH with the integers
corresponding to Q' and Z, and also with those corresponding to Z and W.   If  Z is on the
same side of L as Q', but closer to L, the intersection, if it exists, lies between Z and W and
we shall call FIND_OPPOSITE on the pair Z, W. Otherwise, on the pair Q', Z.

We initiate the procedure by calling FIND_OPPOSITE on the integers 0, n/2.

Each execution of the SPLIT_SEARCH of FIND_OPPOSITE  needs constant time to run,
and reduces the problem to one about half the size.  So we will need about log(n) number
of executions of either routine, which is also the order of the running time = O(log(n)).