600.488 Homework Assignment 1

Due: Wednesday, February 3, 1999

50 Points

Sort the following list of functions of n, so that whenever f is before g, then f=O(g). Functions that are Theta(*) of one another should be listed together.

Show that if f(n) is O(d(n)) and g(n) is O(e(n)), then f(n) + g(n) is O(d(n)+e(n)).

Solution:  f(n) = O(d(n)) is equivalent to the statement that the ratio f(n)/d(n)
remains  bounded as n approaches infinity.

Consider the ratio (f(n) + g(n))/(d(n) + e(n)) =  f(n)/(d(n)+e(n))
                                                                                 + g(n)/(d(n)+e(n)).
This is no larger than f(n)/d(n) + g(n)/e(n).
Since both ratios remain bounded as n approaches infinity, so does their sum. 

Describe three different ways to represent a two-dimensional point.  For each
representation, describe a short method for determining if this point is above or
below the x-axis.

We assume that P is a point on the 2-dimensional Euclidean plane, and
its coordinates are (x, y) in Cartesian form or (r, theta) in polar coordinates.
(In the last case, r is non-negative, and theta is in the interval [0, 2Pi). )

I) Store the coordinates (x, y) of the point.  To answer the question above, check
the sign of y.  If y=0, then P lies on the x-axis.  Otherwise, (y>0)?:above:below
should decide the matter.

II) Store polar coordinates (r, theta) of the point.  The method to determine whether
P is on,  above or below the x-axis reduces then to check whether theta equals 0
or Pi (on the axis),  between 0 and Pi (above) or between Pi and 2*Pi (below).

III) Store homogeneous coordinates (z:x:y) of P as a point in projective 2-space.
It is assumed that  the Cartesian plane is identified with the subset
{ (z:x:y), z not 0} of projective space, by the map taking (x, y) to (1, x, y).
To check whether P is on the x-axis, test if y = 0.  This identifies even the
point "at infinity" on the x-axis.  Now, if both y, z are non-zero, the test
(y/z >0)?:above:below determines whether a "finite" point is above or below
the x-axis.  This convention agrees with (I) in the sense that if we regard P as a
point in the Cartesian plane or as in projective space, the answer is the same.
This corresponds to the following choice of "orientation" in projective space:
of the two oriented line segments connecting the x-axis to P, choose the one
that doesn't contain an "infinite" point.
Observe that if P itself is "at infinity" (that is, z=0 ), then the test cannot
conclude anything consistent, except in the case P lies on the x-axis.  Two
equivalent representations of P will give different answers.

IV) Store "signed" homogeneous coordinates.  Two sets of coordinates
(z_1,x_1,y_1) and (z_2,x_2,y_2) represent the same point if there is a positive
number c such that z_1=c z_2 , etc.  (Oriented projective space.)  Then we
perform the test (y/|z| > 0)?:above:below. This will agree with the Cartesian
results in (I), since we map the cartesian coordinates to signed homogeneous
coordinates which have z = 1 > 0.  Points with y=0 lie on the x-axis if they
have z>=0. The points with y=0 and z<0 are still undefined, but again they
are representations that do not correspond to any point in Euclidean space.

Suppose you are given two polygonal chains, A and B, each represented as a
sequence of two-dimensional points. Suppose further that the sequence of points
in both A and B are ordered by increasing x-coordinates. Describe an efficient
method for determining if the chains A and B ever cross each other (i.e., intersect).
What is the running time of your method?

We label the two-dimensional points in the sequence giving  A as A_0 through
A_n and similarly for B. The number m of segments in B is not assumed equal
to n.  Let P_1, P_2 and P_3 be auxiliary variables storing points and r_1 and
r_2 storing line segments.  I say that a point R is to the left of a point S if the
x-coordinate of R is less than that of S.  I assume that I can decide if a point lies
to the left of another in constant time.  I also assume that intersections of line
segments can be computed in constant time.
(Notice that it is not much harder to compute intersections of line segments than to
compute intersections of lines.  The particulars of this computation will of course
depend on how lines are implemented.) Now I give the algorithm:

1. Start:  Let P_1 store  A_1  and P_2  store B_1.

2. Scan B: while P_2 lie to the left of the point preceding P_1 in  A and B is not
exhausted, let P_2 be the next point in the sequence B. If B is exhausted while P_2
still lies to the left of the point preceding P_1, the algorithm terminates, returning
the empty set {}.

3. Scan  A: while P_1 lie to the left of the point preceding P_2 in B and A has
not been exhausted, let P_1 store the next point in A.  If A is exhausted while
P_1 still lies to the left of the point preceding P_2, return the empty set {}.

4. Compute Intersection: Set r_1 to be the line segment given by P_1 and the
point preceding it in the sequence A.  Let r_2 be the line segment through P_2 and
the point preceding it in the sequence B.  Compute the intersection P_3 of
these segments, and if it exists,  return the set {P_3}.

5. Increment: If  P_2 is to the right of P_1, let P_1 be the next point in A, unless A is
exhausted, in which case we return the empty set.  If, on the other hand P_2 is to the
left of P_1, increment P_2 to the next point in B, or return the empty set if B is
exhausted.  Loop back to 4.

Analysis of algorithm:  Step 1 is executed only at the beginning, and takes constant
time to run.  Steps 2 and 3 are loops executed at the beginning to save computations
in step 4. (We could drop them by modifying slightly step 5.) During their execution
they cause either P_1 or P_2 to be incremented.  The core of the algorithm is the
loop 4-5.  Every time the sequence of steps 4-5 is executed (which runs in constant
time), either P_1 or P_2 is incrementedConsequently the total running time is
O(n + m).

Now, does this algorithm finds one intersection, if it exists?  The initial step 2
eliminates from B the segments which lie wholly to the left of the first segment
in A.  Clearly, these segments cannot be part of any intersection.  Step 3 is
similar, with the roles of  and  reversed.  So when we first execute step 4,
we have a segment in  A and another in B whose projections on the x-line overlap
to some extent.  We check if these intersect.  If they do, we have shown that the
polygonal chains intersect and we are done.  Otherwise, we look at which segment
has right endpoint furthest to the left, and subsitute this by its consecutive in the
respective polygonal chain.  So we eventually check any two pairs of segments
that overlap in the x-coordinate.


Suppose you are given a polygonal chain, A, as in the previous problem, i.e., a chain
whose points are ordered by x-coordinates. Suppose futher that A is already in
your computer's main memory and you know that A is represented using an array. Describe
a very fast method for determining if a given vertical line, L, intersects A, and if so, exactly
where it intersects A. What is the running time of your method?

Solution: We assume that we have a method that runs in constant time and computes the intersection of a line and a line segment (see comment in exercise above).  Let P be the
point corresponding to the intersection of L and the x-axis, and let x be the value of the
x-coordinate of P. We denote by A[i] the i-th element of the array A representing the
i-th point in the polygonal chain A and by x_i the value of its x-coordinate.  Assume i
varies from 0 to n. The algorithm:

Step 1. Check: If either x_n is to the left of x or x is to the left of x_0, the algorithm
terminates and returns the empty set. (So this case runs in constant time.)

Step 2. Initialize: Set y_0 = 0, y_1 = n.

Step 3. Length?: If y_1 - y_0 = 1, skip to step 5.

Step 4. Divide: Let k be the maximum integer less than or equal to ( y_1 - y_0)/2.
If  P lies to the left of A[y_0 + k], set y_1 = y_0 + k.  Else set y_0 = y_0 + k.
Loop back to step 3.

Step 5.Intersect: Return the intersection of L and the segment given by A[y_0] and

Analysis of the algorithm: All steps take constant time and only the loop 3-4 is
executed more than once (perhaps). Each time that loop is executed, the distance
between y_0 and  y_1 is reduced by half, approximately (we may be off by one).
So the number of steps is O(log n) and so is the running time.

In a few words: binary search for the segment that intersects the vertical line.