Algorithm for finding a point among n points in the plane to minimize the sum of the distances

Question

I have a problem with the algorithm. It is different from the usual Fermat Point problem .

Given the set of points n on the plane, I need to find what purpose it is possible to minimize the sum of the distances to the remaining points of n-1 .

Is there any algorithm that you know works less than O (n ^ 2)?

Thanks.

Answer 1

One solution is to assume that the median is close to the average and for a subset of points close to the average that exhaustively calculates the sum of the distances. You can select klog (n) points closest to the middle, where k is an arbitrarily chosen constant (complexity nlog (n)).

Another possible solution is the Delaunay triangulation. This triangulation is possible in O (nlogn) time. Triangulation results in a graph with one vertex for each point and edges to satisfy delauney triangulation. When you have triangulation, you can start at any time and compare the sums of the distances of this point with your neighbors and continue to move iteratively. You can stop when the current point has a minimum amount of distance compared to its neighbors. Intuitively, it will stop at the global optimum point.

Answer 2

I think the main assumption is that you have a dataset that you can easily relate, since many algorithms that would be “good enough” in practice may not be rigorous enough for theory and / or may not scale good for arbitrarily large solutions.

A very simple solution, which is probably "good enough", is to sort the coordinates by Y-coordinate, then make a stable view by X-coordinate.

Take the rectangle defined by the values ​​min (X, Y) and max (X, Y), complexity O (1), because the values ​​will be in known places in the sorted dataset.

Now, working from the center of your sorted dataset, find the coordinate values ​​as close as possible to {Xctr = Xmin + (Xmax - Xmin) / 2, Yctr = Ymin + (Ymax - Ymin) / 2} - O (N) complexity limited by your minimization criteria, distance is the familiar radius of {Xctr, Yctr}.

In the worst case, the difficulty will be to compare your center at every other point, but as soon as you get away from the midpoints, you will not improve the global optimal and should stop searching.