CPSC 643-600: Motion Planning
(aka Robotics Programming)
Fall 1996

Homework Assignment #2

Due: Tuesday October 22 in class.

General Guidelines for Homework

• Be clear and precise. Write neatly and legibly. Justify all answers, even if not specified in the question. Use good judgement concerning how detailed to make your answer.
• If the question is not fully specified, you may need to make some assumptions. In this case, you must state any assumptions you make, and justify why they are reasonable.
• Everyone must turn in their own copy of the assignment. You may consult outside material or work with others (this is encouraged), but you must reference your sources; in particular, list all collaborators on the first page of your assignment.

Do the following exercises.

• Chapter 5: Exercises 4, 6, 8, and 10.
  For exercise 6, give a general description of your method (e.g., describe the modified algorithm clearly using words or pseudo-code) and analyze its complexity. In addition, illustrate your algorithm using a simple example.
• Consider the crossing rule for a critical curve segment B used to determine adjacent cells in the exact cell decomposition for the line segment PQ rotating and translating in the plane (p. 219 in the text).

  It is assumed in the text, that no two critical curves coincide along B. Is this assumption really necessary? Justify your answer. In particular, either prove that it is not necessary or give an example showing how incorrect adjacency information could be inferred if two critical curves do coincide along B.