Wednesday, September 28, 2011
After lecture on Tuesday, a student showed an apparent counter-example to the proof of the line sweep algorithm's correctness. I have updated the slides to cover that case. The algorithm is correct. By the way, it was co-invented by CMU faculty member Michael Shamos. Here is a link to the original paper.