CSIE 922 U0110, MP #3

Spring 2006 CSIE 922 U0110, Programming Assignment #3

Assigned	Tuesday 4/25/06
Due Date	Friday 5/12/06 by 17:00PM

1.: This assignment consists of two parts. One is to compute the density (or the maximum clique size) of a set of intervals and the other is to compute the maximum clique of a set of axis-parallel or iso-oriented rectangles. In the first problem, use the segment tree structure to implement an algorithm for solving a semi-dynamic interval density problem, and in the second problem you need to compute the maximum clique of the rectangles by sweeping a horizontal line from bottom to top and report the maximum clique of the rectangles that have been swept. Use the code for the first problem as a subroutine for the second problem. A graph G(V, E) is called an intersection graph (in this case, an interval intersection graph or interval graph for short) of a set
I = {I_v| vÎV(G)} if I_u Ç I_v¹ Æ iff uvÎE(G). The greatest integer r such that the complete subgraph K^r Í G(V, E) is the maximum clique of G.
2.: Problem 1 : Density of a Set of Intervals
Input: a segment list The set of N (horizontal) segments is entered one at a time. You need to record them, as they will be used later via their indexes. Set up a segment tree for this set of N intervals as a skeleton. These segments or intervals will be inserted into and deleted from the segment tree, which is empty initially. The command (insert or delete) will be done interactively via an input dialog box.
Output: a value, which is the density of the set of intervals or segments in the current segment tree, upon each insertion or deletion command.
3.: Problem 2 : Maximum Clique of a Set of Iso-oriented Rectangles
Input: a rectangle list The set S of N rectangles is given one at a time in the beginning.
Output: a value, which represents the maximum clique (size) of the input rectangles.
4.: Suggestions
In problem 2. You may use a horizontal scan line from bottom to top. When you reach the bottom edge of a rectangle, you insert the edge (or interval) into a segment tree, and when you reach the top edge of the rectangle you will delete the edge (or interval) from the segment tree. Thus the schedule of event (insertion or deletion) is determined once the set of iso-oriented rectangles is known.
Thus, we can use problem 1 to find the density of (semi-dynamic) intervals when they are inserted and deleted.
5.: Your program should be written in C/C++ using object classes available in the library or new objects developed on your own. Documentation of your code is necessary.
6.: Any effort that is beyond the minimum requirement will be recorded for extra credit consideration at the end of this semester. For instance, come up with an animation or visualization of the intermediate results to illustrate the scan-line method in action. If you are interested in other extra-credit work using segment trees, please contact me at dtlee@iis.sinica.edu.tw.
We will select code for inclusion in the geometric software warehouse. Those whose code are selected will be noted in the repository and will be given extra points.