Register Now
Member Count: 626,813 - April 20, 2014  [Get Time]
Login
forums   
Round Tables
News Discussions
Algorithm Matches
Marathon Matches
NASA Tournament Lab
Software Forums
TopCoder Cookbook
High School Matches
Sponsor Discussions
Search Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Forums Round Tables Educational Discussion farthest pair of points [ 1 2 3 ]    NEXT >
farthest pair of points | Reply
We have n points in the plane, and we must find the farthest pair of points. I've seen in Cormen that they belong to the convex hull, is this fact used to actually find them? If yes, how? Is there any other possible solution?
Re: farthest pair of points (response to post by trulo_17) | Reply
Yes, there is at least one O(n^2) solution using convex hull, not sure if it is the fastest solution for this problem but pick each point in the convex full, find the max distance then try the next one.
Re: farthest pair of points (response to post by vexorian) | Reply
Simple testing of every pair would also give O(n^2). Given the convex hull you can get O(n) with rotating calipers method. Also, "diameter" was more effective search term than "farthest points".
Re: farthest pair of points (response to post by trulo_17) | Reply
You may find the following link useful:
http://www.facweb.iitkgp.ernet.in/~arijit/courses/autumn2006/cs60001/lec-compugeo-3.pdf
Re: farthest pair of points (response to post by ulzha) | Reply
Yeah, diameter was a better search term. Just remember closest pair and asume it woud be similar.
Re: farthest pair of points (response to post by TheLlama) | Reply
Thanx man, another interestind pdf.
Re: farthest pair of points (response to post by trulo_17) | Reply
Not sure if this works. My intuition tells me this algorithm:

(1) Construct the convex hull
(2) To find the farthest points on a convex polygon do the following:
(a) Start at point A
(b) Find the farthest point from A by trying them all. Call that farthest point B.
(c) Move clockwise from A so you're at the first point on the hull clockwise from A. Call that point C.
(d) I claim that C's farthest point is either B, or some point clockwise from B.
(e) Keep going clockwise from B, and measure the distance each time. The distance should start increasing, then finally decrease. When it decreases, go back to that longest point. That's the point farthest from C.
(f) Repeat for all the points
(g) I claim that you will measure no more than O(N) lines of distance.


This algorithm's running time is dominated by the convex hull computation. After that, the rest is O(N).
Re: farthest pair of points (response to post by cep21) | Reply
That's exactly what ulzha mentioned with his 'rotating calipers' :-)
Re: farthest pair of points (response to post by broutcha) | Reply
Bah all those fancy math words. Clicked the link and more words! It just confuses meh.
Re: farthest pair of points (response to post by cep21) | Reply
I agree. But I solved the problem in my head (as you probably did) at the point where the convex hull was mentioned, and the algorithm looked like a 'rotating something' so I just assumed that ulzha mentioned the algo I was thinking about.
Re: farthest pair of points (response to post by ulzha) | Reply
Nice page, I guess my solution would be the same as simple testing every pair if all the points already form a convex polygon, couldn't see it.
Re: farthest pair of points (response to post by cep21) | Reply
I agree with you that we don't need fancy names for such a simple method :)

Here's another way of thinking about it.

1) Convex Hull
2) Start at some point A, take point clockwise from it, call it B. Imagine laying the polygon flat on the segment A--B. Draw a bisector through segment A--B. Aything to the right is closer to B than to A, and vice versa.
3) Repeat the following. Move clockwise from B and mark distances to A. Stop until the point reaches or passes the bisector. Then let A=B, B=next point from B. Continue.

It's really easy to prove correctness by induction with this method. And you only need to use cross product to detect when a point passes a bisector.

Frank
Re: farthest pair of points (response to post by trulo_17) | Reply
I used to think this would work:

a) find a random point A
b) find a point B farthest away from A
c) let A:=B and goto b) until repeated 7 times
d) return the farthest pair of points found

But it only finds pairs of points on the convex hull.
Re: farthest pair of points (response to post by rusolis) | Reply
Interesting idea. It's extremely easy to come up with counterexamples, but I wanted to see how it runs on random sets, so I implemented and tested it. I was afraid that contestants might be trying to pull something like that out in problems that require an "honest" convex hull solution and I'm happy that's not the case, even on random cases. On the other hand, in real world applications, 1% error rate might be acceptable.

I used 167 sets of 20000 random points (x,y from 0 to 30000).

The right answer was returned in 58.7% of cases.
The answer differed from the right answer by 0.28% on average.
The algorithm stopped after 3.13 iterations on average.

Another set consisted of 2665 cases, 2000 random points each in the same range of coordinates.

The right answer was returned in 52.1% of cases.
The answer differed from the right answer by 1.11% on average.
The algorithm stopped after 3.07 iterations on average.

edit: some more data: 1299 cases, 10^5 random points each in the same range of coordinates.

The right answer was returned in 51.1% of cases.
The answer differed from the right answer by 0.17% on average.
The algorithm stopped after 3.08 iterations on average.
Re: farthest pair of points (response to post by Krzysan) | Reply
What was the average number of points on the convex hull?
Forums Round Tables Educational Discussion farthest pair of points
Previous Thread  |  Next Thread
[ 1 2 3 ]    NEXT >

RSS