Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Conic Sections/Circles
College Discrete Math

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search