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