Due: April 5, 2006
Written questions:
Programming question:
Write a program to implement the plane-sweep segment intersection algorithm as described on pages 566-568. You can use balanced tree code that was written by someone else, such as from the JDSL library by the book's authors. Your code should generate n random vertical segments and n random horizontal segments, for n = 1,2,4,...,4096 and return the number of segment intersections. Random here means that the coordinate endpoints of the segments are integers in the range 0..1000 chosen uniformly at random. Turn in your source code and the output from your program. Also, time each run of the algorithm and report those results.