I spent all of last night working on my problem set in Geometric Algorithms. Most of this class has taught me to believe that explaining geometry to computers is generally hard. Professor Guibas puts it very well in saying that geometric algorithms have both a numerical and combinatorial aspect to them. It’s an algorithmists worst nightmare.
We spent a very long time on something rather simple: arrangements. Given lines, how do you find all the intersections? How do you represent all the faces? What if they are line segments? It’s a strange problem that you never have to think about. Staring at a bunch of PickUp sticks is easy as pie, but try teaching a computer how to do that.
Clearly, someone was able to do it (i.e. Professor Guibas). It sucks when he’s the one writing the questions for your problem sets though.
