1. For a two-dimensional configuration space, implement the Voronoi diagram using incremental methods.

To generate the Voronoi diagram, I implemented the following procedure:

1. Start at an arbitrary point on the map
2. Move away from the nearest obstacle until equidistant to two obstacles
   1. (Compute the closest point on the nearest obstacle, and move in the opposite direction)
3. You are now on the GVD
4. Move (via linear approximation) along the GVD by passing a line between the nearest point on each of the two nearest obstacles and moving perpendicular to this line
5. Correct your position by performing gradient descent on the gradient vectors w.r.t. the two nearest obstacles so that equidistance is restored
6. When a node (point of triple equidistance) is reached, push the 3 edges leading out of it onto a queue (each edge characterized by the two obstacles equidistant and the node start point [direction is implicit based on order of these two obstacles])
7. Iterate: while the queue is not empty,
   1. Pop an edge from the queue
   2. Follow this edge (via motion along GVD and correction as before) until another node is reached
   3. If we have not seen this node before, push its other two outgoing edges onto the queue
8. The GVD has now been traced out.

Examples

In the above examples, the green dot indicates the chosen start location, and the black dot shows where the process ended (the last node reached).

Source code: Available here

This appears to compile and run fine on linux.andrew.cmu.edu, and should do the same on most other Linux systems. No attempt was made to target other OSes.