Hello community! Please consider the following two problems.
Given $$$N$$$ points on 2D plane, we need to calculate:
A) Coordinates of a new point such that the sum of Euclidean distances from that point to all of given points is minimal (Geometric median finding problem);
B) The index of one of initial points such that the sum of Euclidean distances from that point to all other given points is minimal (Medoid finding problem).
My first hypothesis claims that problem (A) could be solved in $$$O(N\log^2(C))$$$ time (and $$$C$$$ is the absolute value of the maximal coordinate of point) with two nested ternary searches. It is so because of Euclidean distance between given point and some other point is a convex function, and the sum of convex functions is still a convex function, so we can find the global extremum point with ternary search.
I believe I saw that idea a time or two as a suggested solution for Fermat point problem, but I still can't find any mention of this algorithm in papers considering problem (A). So I have some doubts that it may give wrong answer, but I can't find a counterexample.
For the problem (B), my idea is that we can use the solution of problem (A) and then find the point from given array that is closest to the calculated one (or any of such points if there are multiple). But, again, I could not find any mention of this approach in papers.
So I tried to make a stress-test via Polygon to find a counterexample. I use the code that implements an approach described above and a bruteforce code that juct checks all possible points in $$$O(N^2)$$$ time.
Unfortunately stress-testing gave nothing, so I come with two questions for geometry-skilled colleagues:
- Is my approach for problem (A) right? (I believe it is)
- Is my approach for problem (B) right? (I believe it is not). How may the counterexample look like?
Thanks in advance!
