-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$
  • 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. Jul 2 '14 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 Jul 2 '14 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 Jul 2 '14 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 Jul 3 '14 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. Jul 3 '14 at 6:14
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, privacy policy and cookie policy

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