JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Algorithm Discussions Skill-building and Educational Discussion for Algorithm 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 Hull2) 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 Ab) find a point B farthest away from Ac) let A:=B and goto b) until repeated 7 timesd) return the farthest pair of points foundBut 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 Algorithm Discussions Skill-building and Educational Discussion for Algorithm farthest pair of points Previous Thread  |  Next Thread [ 1 2 3 ]    NEXT >