2

Let's say I have an array with CGPoints (wrapped with NSValues). How can I get the two points which are most distant from each other. I mean the distance between these two points is the biggest? I can just check every two points but that does not look efficient. Is there a better way of doing this?

Thanks for help!

Rafał Sroka
  • 39,540
  • 23
  • 113
  • 143
  • 1
    Naively? Test the distances for each combination of points. – Joel Cornett Jun 11 '12 at 09:50
  • 1
    I just found a good duplicate: http://stackoverflow.com/questions/1618398/given-a-set-of-points-how-do-i-find-the-two-points-that-are-farthest-from-each – nhahtdh Jun 11 '12 at 10:04

1 Answers1

5

If there are not too many points (up to 1000, but if intensive, around 100), use the naive brute-force method O(n2).

I haven't read the details, but the biggest distance probably is computable in O(nlog n) with convex hull algorithm + rotating caliper.

nhahtdh
  • 55,989
  • 15
  • 126
  • 162