600.488 Homework Assignment 3

Due: Wednesday, February 24, 1999

Suppose you are given a collection S of n line segments in the plane, each of which is either vertical or horizontal. Design an efficient algorithm for counting the number of pairwise intersections between the segments in S. What is the running time of your method?

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

Suppose you are given a collection S of n points in the plane, one of which is marked as
"special."   Design an efficient algorithm for determining if the special point can be separated
from the rest of the points in S by a line, with the special point on one side and the rest of the
points on the other. What is the running time of your method?

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.

Suppose you are given a simple polygon P that has been triangulated. Suppose further that you
are given two points p and q inside P. Describe an efficient algorithm to list (in order) all the triangles that would have to be crossed by a shortest path from p to q that is constrained to stay in the interior of P.

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

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

Prove by induction (not using the master theorem) that the running time of the 2-variable linear programming algorithm is O(n).

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

Suppose you are given two convex polygons P and Q that are separated by a vertical line, L. Describe a linear-time algorithm for finding a line M that is tangent to both P and Q and also intersects L.

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