Description
1. (20 points) Describe two trade-offs between the Bug 1 and Bug 2 algorithms. Limit your response to
no more than half a page.
2. (30 points) Suppose you are planning for a point robot in a 2D workspace with polygonal obstacles.
The start and goal locations of the robot are given. The visibility graph is defined as follows:
• The start, goal, and all vertices of the polygonal obstacles compose the vertices of the graph.
• An edge exists between two vertices of the graph if the straight line segment connecting the
vertices does not intersect any obstacle. The boundaries of the obstacles count as edges.
Answer the following questions:
(a) (15 points) Provide an upper-bound of the time it takes to construct the visibility graph in big-O
notation. Give your answer in terms of n, the total number of vertices of the obstacles. Provide a
short algorithm in pseudocode to explain your answer. Assume that computing the intersection of
two line segments can be done in constant time.
(b) (15 points) Can you use the visibility graph to plan a path from the start to the goal? If so,
explain how and provide or name an algorithm that could be used. Provide an upper-bound of the
run-time of this algorithm in big-O notation in terms of n (the number of vertices in the visibility
graph) and m (the number of edges of the visibility graph). If not, explain why.
3. (20 points) Let A be a unit disc centered at the origin in a workspace W = R
2
. Assume that A is
represented by a single algebraic primitive H = { (x, y) | x
2 +y
2 ≤ 1 }. Show that if this primitive is
rotated about the origin that the transformed primitive is unchanged. This can be shown by showing
that any point within the transformed primitive H
0 must be within H, and vice versa.
4. (30 points) You are given the endpoints to two line segments, A1B1 and A2B2, in a 2D workspace. The
line segments include their endpoints. Provide an algorithm in pseudocode to compute the intersection
points of these two line segments, if one exists. Be careful and consider all corner cases. Your algorithm
must provide the correct output with every input. Hint: There are many ways to represent line segments.
Choosing wisely will allow for a shorter and more efficient implementation.
