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.

Solution:

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

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 *H *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 *V *in
*H *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 *V *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,

update.

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

the respective x- and y-coordinates of

in

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

time algorithm for finding the two intersection points between a line

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