We are given a circle in the plane and a set of n line segments, such that every segment endpoint lies on the circle. Assume that no two segments share a common endpoint. The goal is to write a program for computing the number of pairs of these segments that intersect.

Let us assume that the 2n segment endpoints are labeled 1, 2, ..., 2n in clockwise order around the circle. A segment is specified as a pair (i, j), where i and j are one of the 2n labels.

The input data is given in a file whose first line specifies n, the number of segments. Each of the subsequent n lines of the file identifies one of the n segments, which is specified by a pair of labels separated by space characters. For, example, suppose n = 5, and the segments are (10, 8), (1,7), (2,5), (3,6), and (4,9). Here is a file that gives this data.

In this example, five pairs of segments intersect. The segment (4,9) intersects with the four other segments; furthermore segments (2,5) and (3, 6) intersect. The intersections are clear if one looks at a geometric visualization.

input visualization

Write a program that asks for an input file that contains the data in the above format, and outputs the number of segment pairs that intersect. The goal is to make the program run as fast as possible. The baseline is the straightforward algorithm that checks each pair of segments for a possible intersection. Your program should certainly be significantly faster than that. Your program should be sequential, that is, it should not resort to any kind of parallelism like threads, GPU, etc. We want to keep the focus on algorithmic ideas in the sequential setting.

On ICON, you should submit your program, instructions for running it, a description of your algorithm ideas and the actual running time on certain input files that I will post later (with n up to a 100,000). I will post detailed submission instructions later as well. We will accept programs in Python, Java, and C.

This assignment corresponds to Exercise 14 of Chapter 1 in Jeff Erickson's textbook.

The homework is due Sunday, February 10, at 11:59 pm.

Update (Posted Feb 1): Here are some sample inputs.

The number of intersections in the small and medium sized inputs above can be found here . These are generated by a program, but I have verified by hand the correctness for the five small sized inputs.

Submission Instructions (Posted Feb 5): Please submit a document that (a) describes your algorithm and any data structures you use in your implementation; (b) the running time in milliseconds on the above inputs with 10,000 and 100,000 segments; and (c) instructions for running your program. In addition, submit the program.

The algorithm description should be detailed enough that we should not have to read your code. When calculating running time, exclude the time for reading in the data from the input file.