Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/