Finding Pairs of Intersecting ChordsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/