-2
$\begingroup$

Given a set $X$ of $n$ points in the real plane, designated by their Cartesian coordinates, find the extreme spread of the points, which is defined by

$\qquad\displaystyle \mathrm{ES} = \max_{1 \leq i,j \leq n}: \sqrt{(x_i - x_j)^2 - (y_i - y_j)^2}$,

i.e. the largest Euclidian distance between any two points in the set. This measure is also known as the diameter of the set.

$\endgroup$
6
  • 1
    $\begingroup$ What's wrong with just computing that value directly? You have a formula to compute the extreme spread; is there some reason why simply evaluating that formula is not sufficient for your needs? Actually, what is your question? I can't tell. You should tell us where you are stuck and what your question is. What are your thoughts? What have you tried and where did you get stuck? We expect you to make a serious attempt on your own before asking, and tell us what you've tried and what research you've done on your own before asking here. $\endgroup$
    – D.W.
    Commented Jul 2, 2014 at 22:39
  • $\begingroup$ I'm looking for an efficient algorithm to compute the value. The O(n^2) solution is trivial, of course. I know that a Convex Hull can be found in O(n log n) time, and then the extreme spread can trivially be calculated in O(m^2) where m are the number of points on the Hull. I suspect there is an O(n log n) algorithm for the extreme spread. But like you said, this is probably part of a thoroughly researched family of geometric problems so I didn't want to spend time reinventing the wheel. So, for example, if you know the canonical name for this exact problem that may be a sufficient answer. $\endgroup$
    – feetwet
    Commented Jul 2, 2014 at 23:52
  • $\begingroup$ BTW, you already showed me something interesting today by downvoting my first question: It's not possible to have non-positive rep on SE! $\endgroup$
    – feetwet
    Commented Jul 2, 2014 at 23:53
  • 1
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – FrankW
    Commented Jul 3, 2014 at 5:39
  • $\begingroup$ feetwet, great! I encourage you to edit your question to clarify that in the question. The purpose of this site is to build up an archive of high-quality questions and answers that will be useful not only to you, but also to others as well. You can click the "edit" button underneath your question to edit the question. $\endgroup$
    – D.W.
    Commented Jul 3, 2014 at 6:14

2 Answers 2

1
$\begingroup$

Best answer so far is on SO which suggests using Convex Hull ($O(n \log n)$) followed by Rotating Calipers on points in the Hull, which is $O(n)$.

This problem was also posed as TFOSS and a number of efficient solutions can be found here.

$\endgroup$
1
$\begingroup$

This is called the diameter problem or the farthest pair problem. There's lots of research on the topic. You might want to go read some of the papers. It can be done in $O(n \lg n)$ time in 2 dimensions; see, e.g., here. See also Wikipedia on proximity problems.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.