Homework One. Solutions. Due February 6 at the beginning of
class. Late homeworks will not be accepted.
Problem 1:
Given a convex polygon P, and a point w that is outside of P, we say
that a point q on the boundary of P is visible to w if the open line
segment wq does not intersect P. (the open line segment does not
contain w or q, just all the points between them).
For this problem,
suppose P is an n-sided convex polygon that is enclosed by a circular
disk C. Our goal is to make an O(n) algorithm that determines if
there exist two points w1 and w2 that are outside P, inside C, and
together see every point on the boundary of P. If these points exist,
we need to output such a pair of points.
To solve this problem, follow the following three steps:
(a) First, show that if two such points w1, w2
exist, then they may be assumed to be on the boundary.
Suppose two points w1, w2 exist that are not on
the boundary. Point w1 "sees" some subset of the edges,
lets call these edges e1 ... ek. If we extend the farthest apart
edges e1 and ek we get the boundaries of the region of points which
can view all these edges. The (open) intersection of
this region and the circle C is the (open) arc of points on C that see
these edges. Any point in this arc serves as a new w1. The same
argument applies to w2. So if w1 and w2 exist inside the curve,
then a pair of points also exists ON the curve.
(b) Explain how to subdivide the boundary of C into circular arc
intervals such that all points within each interval "see" the same
edges of P. Show that this can be done in O(n) time.
This is a little trickier than it seems. We are going to make a
circular linked list with N elements, which has the BACKWARDS GOING
extension of each segment with the circle. That segment is the FIRST
segment that this arc segment sees. Then we go through the list again
and put in the FORWARD going extension of each segment with the
circle. This requires that we subdivide (or duplicate) the list
element where this segment intersects. As we go we update the each
list element with the LAST segment that it sees. (it necessarily sees
all segments between the first and last). [warning, solution not proofread].
Algorithm:
new START;
START.first = p0;
START.number = 0;
let q = intersection of circle and extended segment FROM
p0, through pn-1
START.theta = angle from x-axis to line from center of circle to q,
Y = START
For i = 1 to n-1
new X;
X.first = pi;
let q = intersection of circle and extended segment FROM pi, through p(i-1)
X.theta = angle from x-axis to line from center of circle to q,
Y.number = i;
Y.next = X;
Y = X
end
X.next = START
for i = 0..n-1
extend segment pi,p_i+1 until it intersects the circle at point q
theta = angle from x-axis to line from center of circle to q,
while X.theta < theta
X = X.next;
X.END = i;
end
duplicate X to become X1 X2;
X1.prev.next = X1;
X1.next = X2;
X1.END = i;
X = X2;
end
Idea:
(c) Use (a) and (b) to present an O(n) time algorithm for this problem.
Idea: Start at segment a. move segment b around until it "just barely
stops overlapping with a". if b and a together see every edge, then
we're done. otherwise, try the next a.
a = 1;
b = 2;
while b.first <= a.last
b = b.next
end
if b.last >= a.first
output any points in a and b.
else
a = a.next
end
Problem 2: Suppose you are given a convex polygon P, with
n vertices in counter-clockwise order (stored in an array). Show how
the find the following in O(log n) time:
(a) Given a linear function f(x,y) = ax + by, find the vertex of P
that minimizes the values of this function. (One function might be
f(x,y)=0x+1y, in which case the point that minimizes the function is
the lowest point of the polygon).
(b) Given a point w outside the polygon, find a tangent vector (a line
through w that intersects only one point of the polygon).
Lemma: Find smallest point in an array of points M that may get larger,
smaller, then larger again.
Algorithm:
a = 1
b = n
while (a-b)>1
mid = a+b/2;
if M[a] > M[a+1] and M[mid] > M[mid+1] % increasing at point a and midpoint
if M[a] < M[mid]
b = mid
else
a = mid
end
% decreasing at point a and midpoint
elseif M[a] < M[a+1] and M[mid] < M[mid+1]
if M[a] < M[mid]
b = mid
else
a = mid
end
% increasing at a and decreasing at mid
elseif M[a] > M[a+1] and M[mid] < M[mid+1]
a = mid
% increasing at mid and decreasing at a
elseif M[a] > M[a+1] and M[mid] < M[mid+1]
b = mid
end while loop
Problem (a),(b) can both be done with this Lemma. In problem (a),
substitute a xi + b yi for the value of an array
location M[i]. For problem (b), substitute angle of
(-inf,0),w,pi for the value of array location M[i].
Problem 3: A polygon P is star-shaped if there exists a point q inside
the polygon such that for every point p in the polygon P, the line pq
is contained within P. You are given the polygon P as a
counterclockwise list of vertices. Give an O(n) algorithm to compute
the convex hull of P. Prove the correctness of your algorithm -- (at
least argue that every edge of your output is actually on the convex
hull).
We mimic Graham's scan:
relabel points so that x_1 = farthest left point and all the rest are
still ordered counterclockwise around point q.
make fake point x_0 = <0,infinity>
push x_0
push x_1
push x_2
for i = 3..n
push x_i
while size(stack)>2 and orient(stack.second, stack.first, x_i) = "right turn"
pop stack
end
end
Correctness:
Every point q is initially put on the hull. A point q is discarded
from the convex hull if and only if it lies in counterclockwise order between
points p_i, p_k and p_i, q, p_k is a right turn. Such a point q can
never be on any convex hull.
Problem 4 (hard): Given a path p1,p2,p3,... pn, that ALWAYS
TURNS left, give an O(n) algorithm to determine if the path has any
self intersections. (you may assume a constant time subroutine for
checking if a pair of segments intersect).
see solution to problem 5, pages 4-6 of: http://www.cs.umd.edu/~samir/754/s2.ps">link