5
\$\begingroup\$

What is the least computationally complex way to find two points such that the distance between them is greater or equal to any other pair.

Remember hearing something about how you could find such a pair by randomly picking a point r, finding the point furthest away fa and then finding the most distant point from it, md. The diameter is then the distance between fa and md (i.e norm(fa - md)). Is this correct? Can you prove or disprove it? What is the correct way if this is incorrect?

Improve this question
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Diameter is not well defined for a general set of points. Please define more precisely what you are looking for. \$\endgroup\$
    – Pieter Geerkens
    Oct 10, 2015 at 5:28
  • \$\begingroup\$ @PieterGeerkens You are right, I borrowed this from Graph Theory. \$\endgroup\$
    – AturSams
    Oct 10, 2015 at 17:36

3 Answers 3

Reset to default
5
\$\begingroup\$

It wont be correct. If you take 4 points; 3 of which lie on a circle and the 4th is in the center. The diameter of this set is the distance of 2 points on the circle. Your algorithm may choose the other point which won't have a distance like that.

The proven correct way is to create the convex hull and use the Rotating Calipers method for finding the largest distance.

This ends up being O(n log n + k) time complexity. O(n log n) for creating the convex hull and O(k) for iterating over then entire hull to find the points the furthest apart.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Your explanation is not clear. I can't understand why the OP's approach is not valid, and how your "4 points" relates to it. \$\endgroup\$
    – JPhi1618
    Oct 8, 2015 at 16:42
  • \$\begingroup\$ @JPhi1618 To visualize ratchet's complaint about the OP's approach, consider the case with exactly 3 equidistant points (equilateral triangle). The OP's approach will calculate the length of a triangle's leg as the diameter. What is more often desirable though is to visualize the 3 points as part of a curved shape (circle in this case) and to take the diameter from that; which is what this answer describes. \$\endgroup\$
    – Steven Hansen
    Oct 8, 2015 at 18:06
  • \$\begingroup\$ @StevenHansen Ok, thanks - that clears it up. If we define "diameter" as longest distance between two points, is the OP's algorithm acceptable? If we have a cloud of 1000 points, I think in most instances the fastest, reasonably accurate approach would be desired. \$\endgroup\$
    – JPhi1618
    Oct 8, 2015 at 18:11
  • \$\begingroup\$ @JPhi1618 Even with this new definition of "diameter" there are problems. There is not enough room in a comment, so I've posted an answer that you can examine for an explanation. \$\endgroup\$
    – Steven Hansen
    Oct 8, 2015 at 19:46
5
\$\begingroup\$

There is already an answer for:

What is the correct way if this is incorrect?

You should only ask one question at a time. I'll cover:

Is this correct? Can you prove or disprove it?

Also, it was questioned in comments whether the OP algorithm might be "good enough" even if it isn't the diameter from a curve. Bottom line: you aren't guaranteed to get the two points that are furthest from each other.

Consider the point cloud with exactly four co-planar points, { A, B, C, D }. AB = AC = r, BAC = 70 degrees, ABC = ACB = 55 degrees, and Dis halfway along BC.

Like so:

          A

    r           r

B         D         C

Bottom line (TLDR;) using OP algorithm: if D is the random point, the next point is A, then either B (or C: same distance). OP algorithm yields AB or AC. However, the longest distance is BC. The algorithm fails in at least this case.

Math Proof:

  • From random point D we compare AD and BD. AD = r*sin(55) and BD = DC = r*cos(55). Since cos(55) < sin(55), AD > BD and point 2 is A.
  • From A we consider AD and AC. AC = r and r > r*sin(55), so AC > AD and the final point is C (or B: same distance).
  • Final OP diameter is AC = r.

However, BC = 2*r*cos(55) which means BC > r. The furthest two points from each other are B and C, not A and C.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ What if you keep at it a few times, does it converge? \$\endgroup\$
    – AturSams
    Oct 9, 2015 at 18:03
  • \$\begingroup\$ There are situations (such as you seem to have found), where the wrong points keep pointing back to themselves. \$\endgroup\$
    – Steven Hansen
    Oct 9, 2015 at 19:44
0
\$\begingroup\$

Ok..

Let's look at the following shape:

   B
  / \
 A   C
  \ /
   D

Now, lets say, the distance BD is 5. The distance AC is 4. If you pick A, you will get C at a distance of 4. From C you will get A again. The distance AD = CD = CB = AB is from Pythagoras:

sqrt((4/2)^2 + (5/2)^2) = ~3.2

So yeah, you can miss the mark with a diamond shape.

Improve this answer
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .