farnasirim's blog

By farnasirim, history, 6 years ago,

Hi.

As always the question can be stated fairly easily:

Given a set of points on a 2D plane, how to find a point (x, y) on that plane such that sum of the euclidean distances between the chosen point and the given points is minimum (among all possible choices of (x, y))?

How about finding the same thing in a 3-Dimensional space?

Thank you for the time you put on reading this and thanks in advance for sharing your solution/idea.

• +21

 » 6 years ago, # | ← Rev. 2 →   0 I misunderstood the problem, Ignore
•  » » 6 years ago, # ^ |   +10 because you don't care about the points inside the CH wtf?
•  » » » 6 years ago, # ^ |   0 I meant you don't care about the points in the set which are inside the convex hull. It's so because the diameter will always be a pair of the Convex Hull's vertexes.
•  » » » » 6 years ago, # ^ |   +20 But the diameter has nothing to do with the problem in this entry...
•  » » » » » 6 years ago, # ^ |   0 Lol, just understood that I misunderstood the problem :DSorry the solution is to a completely different problem.
•  » » 6 years ago, # ^ |   +35 You minimize the maximal distance between the center but not the sum of them. The solution of the original problem is to run two ternary searches: on x and y coordinates, one into another. The proof is based on the fact that the sum of the convex functions is a convex function.
•  » » » 6 years ago, # ^ |   0 Should the two ternary searches be independent or should they be nested?
•  » » » » 6 years ago, # ^ |   0 When in the first ternary search you fix some x, then you run ternary search on y in fact on the segment [(x,  - ∞), (x,  + ∞)].
•  » » » » » 6 years ago, # ^ |   0 Thanks. That does the job.
 » 6 years ago, # |   0 Why is simple ternary search the bad idea?
•  » » 6 years ago, # ^ |   0 This would mean that the point we are looking for is (x, y), where x and y are the "center"s of the projection of the set of points onto the x axis and y axis respectively. Right? Can you prove the correctness?
•  » » » 6 years ago, # ^ |   +5 Distance to some point is convex function. Sum of convex functions is also a convex function. Isn't it enough?..
•  » » » » 6 years ago, # ^ |   0 Yepp it is. Thanks.
 » 6 years ago, # |   0 This point is called Fermat-Weber point. For n=3 we get famous Torricelli point. But in my opinion for other n it is #P complete problem.
•  » » 6 years ago, # ^ |   +23 But anyway, for each ε there exists an algorithm polynomial on , finding the point with precision ε. I think that for ε = 0 you simply can't output precise answer, when it is irrational, so I don't think we can consider this problem as a #P problem, or we need to find a way to express the answer in the other form.
 » 6 years ago, # |   0 What if we want to find one of the given points that have minimum sum?