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.
Solution:
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 incremented. Consequently
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 A and B
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
A[y_1].
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.