Solution: We order the vertices according to the following relation,
which defines a total
ordering of the points on the plane. Let P =(x1, y1) and
Q=(x2, y2). Then P precedes Q if
either x1 < x2 or x1 = x2 and y1 < y2.
We keep the following data:
i) An ordered list (or priority queue) of all vertices of vertical segments, V.
ii) An ordered list (or priority queue) of all vertices of horizontal segments, H.
iii) The data consisting of horizontal segments should be searchable
under either of its
endpoints, something we can accomplishing by building two ordered dictionaries
with appropriate keys. Do the same for vertical segments.
iv) A basic event will be the x-coordinate of a vertical segment.
So we use the plane
sweeping paradigm.
General step: If v is an event (an x-coordinate
value from a vertical segment), select
all horizontal segments which have left endpoint to the left of v.
Using the endpoints
from H as events, check first whether these segments share the
same y-coordinate.
For any y-coordinate shared by multiple horizontal segments,
process these segments
left to right, by using the endpoints as events. Set a counter c=1.
As you proceed to check
for overlaps, c is the number of leftendpoints minus rightendpoints
found along the way.
Thus we can process endpoints rather than segments and still count
intersections correctly
by multiplying them by c. We just add c intersections
whenever we find a leftendpoint
and c is not 0.
Next remove from H all edges whose right endpoint is also the the left of v.
Select all vertical segments that have v as coordinate of an
endpoint. Take the vertex Bv
with lowest y- coordinate and set a counter r = 1.
Jump to the next vertice above Bv. Count
how many horizontal segments have y-coordinates between that
of v and Bv. These are
intersections. Maintain the invariant that r should count the
number of bottonendpoints
minus topendpoints found along the way. Intersections shall be
counted with multiplicity
r, both for the overlapping of vertical segments and for crossings
of horizontal and
vertical segments.
Running time: The dictionaries could take time O(nlog(n))
to build. Consecutive searches
then take time log(n) to perform, or constant time to find the
next element. We have O(n)
events to process. Each of these events might take O(k+log(n))
to perform, where k is the
number of intersections associated to the event. Thus the total running
time is O(k +nlog(n)).
Solution: Let P be the special point, and T be a stack
containing all points of S except for P.
Then if T has only one element Q let a be the orthogonal
bisector of the segment from P to Q.
Then a is a line separating P and Q. If T
has at least two points, we will have to measure
angles. All angle measurements will be made with respect to P.
Pop Q and S from T
and order them as P_1, P_2 in such a way that the angle traversed
counterclockwise from
P_1 to P_2 is less than half turn. If P, P_1
and P_2 are colinear and P is in between P_1
and P_2 then such angle does not exist, neither there is a line
separating P from P_1 and P_2.
So we may assume that we can order the points as above. Let d
be the minimum of
dist(P_2, P) and dist(P_2, P).
Continue, popping another point P_k from T and checking
whether:
i) P_k lies in the ray from P to P_1, or in the ray from
P to P_2, or within the convex
region described by these rays. This can be readily computed by comparing
the slope
of the segment connecting P_k to P with those of the
mentioned rays. Discard P_k after
replacing d by minimum of d and dist(P_k, P).
ii) P_k lies within the convex region between the rays going
from P in the opposite
directions of P_1 and P_2, or on those rays.
Then there is no line separating P from the
set {P_1, P_2, P_k} and we are done.
iii) P_k lies within the convex region described by the ray from
P in the opposite direction
of P_2 and the ray in the direction of P_1. Then P_k
comes "before" P_1. Replace P_1
by P_k, and d by minimum of d and dist(P_k,
P).
iv) P_k lies within the convex region described by the ray from
P to P_2 and the ray leaving
P in the opposite direction of P_1. Then P_k
lies "ahead" of P_2. Replace P_2 by P_k and
d by the minimum of d and dist(P_k, P).
If we have emptied T and (ii) never occurred, then there is a
line separating P from the rest
of S. Let theta be half of the angle from P_2 to
P_1. So theta is an acute angle. Let r be the
ray bissecting the convex region described be the rays through P_1
and P_2. Trace a line
a perpendicular to r, and intersecting r at a distance
equal to (d/2)cos(theta) from P. Then
the line a separates P from the rest of the points.
Since each computational event was associated with processing a point
from T, plus some
constant time computations at the beginning and end, then our algorithm
runs in time O(n).
Obs.: I assumed that S was not presorted in any fashion.
If it is, it may be possible to
use that order to find the final P_1 and P_2 (giving
widest angle) in logarithmic time,
or decide that the separating line does not exist. In that case,
the whole algorithm would
also run in logarithmic time.
Solution: I will first describe a method that runs in time O(n),
where n is the number of
vertices in the original polygon, and then we describe one that runs
in time O(r), where r
is the number of triangles traversed in the path from p to
q.
Method 1: We translate the problem into a minimum-distance traversal
of a graph G.
For each triangle of given triangulation, create a vertex of G,
and connect two vertices of G
whenever the triangles they refer to share an edge in the triangulation.
So G is the dual
graph of the triangulation.
I claim that G has no cycles. This is because a cycle in
G defines a face in G and by duality,
would enclose a vertex of the original polygon. But we
are not allowed to seek paths
outside the polygon and so we will never enclose a vertex.
Since G is a tree, there is a unique path from the dual of T_p,
the triangle containing the vertex
p, to the dual of T_q. Finding the path and
storing the vertices of G (duals of triangles in the
given triangulation) can be done by standard continuous graph traversal
methods, such as depth
search.
In the implementation, the two steps mentioned above (creation of G
and traversal) should be
done simultaneously (that is, we build G as we make our way
from p in each possible
direction). Then as soon as we find one path to q, we
may abort the other attempts.
Running time: Building G and traversing it will in general
take as much time as there are edges
plus vertices in G. Each edge in G comes from an
internal edge in the original triangulation,
and since each triangle contributes with 3 edges, the number of edges
in the triangulation
(internal and external) is (three times the number of triangles + number
of vertices in
original polygon)/2. Using Euler's characteristic, we get that
the number of triangles is n-2,
where again n is the number of vertices in the polygon P.
The number of edges of G is then
n-3. The number of edges plus vertices in G is
thus 2n - 5. Hence the running time of O(n).
Method 2: This method will run in time O(r), where r
is the number of triangles in the path
from p to q.
If p or q are already vertices of the original polygon,
we keep them. Otherwise we look at
the triangles T_p and T_q containing p,
q. (It might happen that p lies on an edge, and
therefore is contained in two triangles. In this case, just work
with both of them. Same
observation valid for q.) Next consider all vertices of
T_p and T_q, and label them
p_1, p_2, p_3, q_1, q_2 and q_3. Starting
from each of p_i, q_i, i=1..3, move on each
direction along the boundary of the polygon until one of the other
points is reached.
If from p_1 in some direction we reach another p_i before
any q_j, then just disregard
this path. As soon as a path is found from a p_i to a
q_j, stop the search, ending up with
the shortest path along the boundary of the polygon, from a p_i
to a q_j. Since we performed
at most six similar searches, the computation time up to now is of
the order of the number
of edges along this path.
Say that p_1 > a > b > ... > z > q1 is the shortest path
above, where the intermediate letters
designate the vertices along the boundary of P connecting
p_1 to q_1. Then trace a segment
from p to p_1. Centered at p_1,
rotate the segment to p either clockwise or
counterclockwise, choosing the direction that will bring this segment
to lie along the edge
from p_1 to a just before it swings out of the polygon.
As you move in this direction,
enqueue all triangles the segment sweeps by. Then add the triangle
with edge p_1 - a and
move on to the vertex a. Continue this sweeping action in each
vertex, hopping on to the next
vertex until you reach q_1. On q_1 you do the same procedure,
finishing when you reach
triangle T_q. Notice that the number of operations used
to enqueue triangles is roughly
proportional to the number of triangles themselves in the path from
p to q. It is also clear
that the shortest path inside the polygon must cross this triangles
(or touch them on a vertex),
because every triangle in the triangulation of P touches
the boundary and the shortest path
can be "projected" onto the boundary to give the shortest boundary
path. Also since each
edge on the boundary path is the edge of a triangle in the final path,
then the total running
time is at most O(r).
Solution: Since we know the algorithm terminates, it solves the first
few values of n in O(1)
time. We must show the induction step.
First, our algorithm is recursive. It performs an amount of computation
which is clearly
proportional to the input size n, and then e xecutes a recursive
call on a problem which has
input size at most 3n/4. Let c be the constant
of proportionality that accounts for the work
done in each recursive instance. If T stands for
the running time, then we have:
T(n) <= cn + T(3n/4).
Since 3n/4 is less than n, the induction hypotheses gives T(3n/4) = 3bn/4, for some constant b.
Thus: T(n) <= n(c + 3b/4) <= bn.
(As long as we are not too greedy and accept the restriction b >
4c.)
Solution: Without loss of generality, we assume that P is
to the left of Q and that the maximum
y-coordinate of the vertices of P is larger than the
corresponding coordinates of Q. Let p be
the highest vertex in P and q that in Q.
This can be found in log(n_P) + log(n_Q), using a
binary search. n_P and n_Q are the number of vertices
in P and Q, respectively.
If the line from p to q crosses either polygon,
it will do so to the right of p in P and to the
right of q in Q. (It slants downwards from these
points.) Notice that, if the line pq
crosses Q, then the edge to the right of Q, if extended
as a ray towards p, will pass under p.
We search for the first edge which has positive slope, and return to
q in a binary search
for the first edge that when prolonged to the right, will leave some
part of P below.
Notice that to check whether a given prolonged edge leaves a given vertex
of P below
takes constant time. To check whether a given edge leaves at least
one vertex below
takes logarithmic time in n_P, using binary search methods.
Checking whether some
edge of Q leaves any of P below takes O(log(n_P*n_Q))
= O(log(n_P) + log(n_Q)).
By symmetry, we spend the same computational time to find the last edge
of P that will
leave some of Q above. A line connecting the right end vertex
of the edge found in P to the
left end vertex of the one found in Q will be the tangent sought.
Here below a view of the edge e2 of P which is the last
to leave some of Q
above, but is preceded by e1 which does not have that property.
A line connecting
the vertex in between e1 and e2 to q is clearly
the tangent. (We here have changed names
and q refers to the vertex in Q having properties as
the vertex between e1 and e2.)
