1

Let's say I have a set of points: (i.e. in my case, a list holding all points: pts = [(1,1),(3.4,5),...,(x,y)]). I would like to understand what the fastest approach to finding the maximum distance between two points is. Return the distance and the points used.

I understand that traversing through each point is computationally expensive and would result in O(n^2).

Another approach would be to compare pt1 -> pt2, pt1 -> pt3, etc. then essentially store pt2 -> pt1 (which is the same as pt1 -> pt2), but perform pt2 -> pt3, pt2 -> pt4, etc. I feel like this would give me at least O(n^2 / 2) but still computationally expensive.

Is there any approach, obviously after finding Convex Hull which is O(n log (n)), to use that smaller finite set of Hull points to determine what the maximum distance is - still within O(n log(n))?

Thank you!

sgerbhctim
  • 3,420
  • 7
  • 38
  • 60
  • Most of these answers are revolved around Convex Hull - which I understand how to build that algo.. rotating calipers dont help much either.. Wanted to have a more cohesive discussion around distance between points specifically. – sgerbhctim Jan 21 '19 at 16:10
  • Rotating calipers is *O(n)* after finding the convex hull, where *n* is the number of points in the convex hull, not in the original point set. Why does that not help much? What more are you looking for. – beaker Jan 21 '19 at 16:22

0 Answers0