Hi everyone,

In this tweet by MIT CS professor Ryan Williams, he writes:

Lijie Chen
@wjmzbmr1
Jul 25
The problem statement is extremely simple: given n d-dimensional points, find two points with maximum Euclidean distance.
The best algorithms (3 decades old) run in n^{2-o(1)} time for d=omega(1),
Can we show there is no n^{2-eps} algo time for super-constant d, under SETH?
Quote Tweet
R. Ryan Williams
@rrwilliams
Jul 22
Lijie is trying to convince everyone at the CCC rump session to work on furthest pair

I found what looks like an answer to this problem--it's a good approach and I don't care to take the time to fully evaluate if it is provably correct--it's an intuition that looks good; it looks like there is a O(m^1) algorithm for this task. I am not writing a proof right now--I'm not seeking a position as a mathematician, although I could write proofs if asked on the job. The algorithm is partly based on these two sources:

https://mathworld.wolfram.com/Circumcenter.html
https://datascience.stackexchange.com/questions/35641/how-to-find-4th-point-equidistant-from-3-other-points

The idea is, if you had three points in (e.g.) 3-space, you would draw a plane that intersects with all 3 points in d-dimensional space, connect the three points on the plane to form a triangle, and find the circumcenter. This point is equidistant from all three points. By inspection (proof omitted, see Wolfram source), the point is closest to the edge of the triangle that connects the two furthest apart points.

When d >= n, in d-dimensional space with n points, find the (n-1)-dimensional version of a plane (it's the equivalent of Cartesian space, but "at an angle" that allows it, in a higher dimension, to connect points arranged in a particular way). Now, connect the appropriate multidimensional shape between the points, find the (quasi-)circumcenter for this shape, and locate the closest side of the object (it might be multidimensional here). This is the edge that connects the two furthest apart points.

If d is too small, look to see which points are "enclosed" by some of the other points; such enclosed points cannot be in the pair of furthest points and can be eliminated. Continue eliminating points until d >= n, and then apply the process above.

Of course this is not a thoroughly evaluated or proved solution, but I chose to only take less than half an hour to present an approach. I assert that it is either correct or fixable, i.e., I could fix it and find a proof of correctness of my approach within 3 hours. I'm not positive of this, but I really think so.

Clearly, the algorithm runs in linear time. You just draw a k-dimensional version of a plane, draw a shape to connect the points, find the multidimensional version of a circumcenter, and find the nearest (multidimensional) side; this will be the furthest apart pair of points...unless I'm mistaken and would need to re-do part of this if I were being more thorough.

-Philip White (philipjwhite@yahoo.com)