Finding Pairs of Intersecting Chords

Date: 07/24/2000 at 13:23:09
From: Srikant
Subject: n intersecting chords in a circle

Hi,

Problem 15.1-8 page 286 in "Introduction to Algorithms," Cormen, 
Leiserson, Rivest.

Consider n chords on a circle, each defined by its endpoints. Describe 
an O(n*ln(n)) algorithm for determining the number of pairs of chords 
that intersect inside the circle. (For example, if the n chords are 
all diameters that meet at the center, then the correct answer is 
n_C_2.) Assume that no two chords share an end point.

My work so far:
Consider 2 chords AB and CD with endpoints (x1, y1), (x2, y2) and 
(x3, y3), (x4, y4) respectively.

            C
            |
            |
     A---------B
            |
            |
            |
            D

For AB to intersect CD the following must be true:

     x1 < x3 < x2
     x1 < x4 < x2
     y1 < y3
     y2 < y3
     y4 < y1
     y4 < y2

Consider the set of n chords = {1, 2, 3, ..., n}.

By comparing the coordinates of each chord with those of chords later 
in the set I can figure out the number of pairs of intersecting 
chords.

     For chord 1, number of comparisons   = n-1
     For chord 2, number of comparisons   = n-2
      :                                     :
     For chord n-1, number of comparisons = 1

Summing these from i = 1 to n-1, I get (n-1)n/2 = O(n^2).

The problem requires that I solve this in O(n*ln(n)) time.

Is there any other property of chords in circle that I can use to cut 
the time from n^2 to n*ln(n)?

Thanks a lot,
Srikant

Date: 07/24/2000 at 23:30:41
From: Doctor Peterson
Subject: Re: n intersecting chords in a circle

Hi, Srikant.

Your proposed way to determine whether two chords intersect is wrong; 
for example, it's not necessary that A be to the left of B (x1 < x2), 
or that C and D be between them. I would approach it instead in terms 
of the position of each point around the circle (which requires you to 
find the center of the circle and each point's angle relative to that 
center.) Then two chords AB and CD intersect if and only if the 
points' order around the circle is ACBD or ADBC; that is, if A and B 
separate C and D from one another.

I'll leave you to think about an algorithm for doing this check on all 
the chords. As in sorting, you've found that the obvious algorithm is 
not the fastest. O(n*ln(n)) suggests that you will want to find some 
divide-and-conquer technique along the lines of a heapsort or 
quicksort, whereas your attempt is like a bubblesort. You don't have 
time to compare each chord with every other chord to see if they 
intersect. Think about techniques you've learned for problems like 
sorting, and see if they might apply here.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/