Given M source points (s-points), determine N, the number of destination points (d-points), and their locations (coordinates), such that the sum of the N Euclidean distances from each source point to the N destination points is equal. Write this function E(M)=N.
It is known that E(2)=1 (midpoint of a line segment), E(3)=1 (center of a circle), E(4)=E(5)=2 (focal points of an ellipse).
Specifically, this question is, is E(6)=3, and in particular, how are the 3 destination points determined?
It is hypothesized that E(M) = floor(M/2).
The questions above come to life in the following:
There are 6 friends that live in different locations, and they get together monthly. They are friends, so they want to treat each other equitably. Specifically, they want to make sure, over time, that they each travel the same distance to meet. They also want to make sure they are not traveling longer than needed - they don’t want to waste time traveling, they would rather be seeing each other. [I.e. when they travel, they will travel in a straight line to their destination.]
If they are all on a circle, they could all travel to the center of the circle, and thus their travel distance is the same as each other. But it is unlikely that they live on a circle. [BTW, if there were only three friends, they could, except in degenerate cases, find a circle.]
If they all live on an ellipse, they could, in the first month, travel to one focal point and meet there, and in the second month, travel to the second focal point and meet there. Thus, every two months, they would have all traveled the same distance as each other. It is unlikely that they live on an ellipse. [BTW, if there were only five friends, they could, in most cases, find an ellipse.]
For six friends, it is (highly confidently) hypothesized that they need three meeting places. In the first month, they meet at meeting point 1, in the second month, they meet at meeting point 2, and in the third month, they meet at meeting point 3. The distance each of them travels in three months are equal. [There are degenerate cases, which will be discussed below; let’s defer that until later.]
Q1: Are three meeting points sufficient for the six friends to meet? [It’s clear that two meeting points are insufficient; six general points do not fall on an ellipse. If the condition was relaxed that they no longer have to travel the minimum distance (i.e. in a straight line each trip), then the 3 friends on the left could go to the center of their left circle then on to the center of the right circle the first month, and the three friends on the right could just meet them there, and reverse the procedure the second month, thus two points would suffice. There are other, more convoluted solutions that are sub-optimal…]
Q2: This is the primary question - Given the 6 locations of the friends, how are the three locations determined? [Assume a flat map and Euclidean, as-the-crow-flies distances.]
Q2a: If this is solved algebraically, what power of equations / an equation needs to be solved? (I got a set of six 8th power equations in 6 variables after eliminating radicals. Are there simpler equations that can be created / derived / solved?)
Q2b: If this is solved geometrically, what are the steps (connect these points with a segment, bisect it, draw an arc with center at ….)? (I made no progress with this approach.)
Q2c: If this is solved computationally, what approach should be followed, and what are the issues to be careful of? (I used multiple random starting location sets with a gradient approach, but ran into too many local minima, and had to make my granularity so small that the computation time exploded. In the end, I concluded this was not a feasible approach.)
Q2d: Are there other methods to try: transformations and projections and …?
Q3: What are the interesting, trivial, degenerate, constrained, or exceptional cases not yet mentioned (circle, ellipse)? Specifically how can you tell when a set of points does not have a solution? And in those cases, will four meeting locations suffice?
Q4: If, instead of using Euclidean distances, Manhattan distances are used, then (surprise!) using the top left corner and bottom right corner of the bounding box for the two meeting points satisfies the problem! What other interesting results are there in the Manhattan distance case?
Q5: If there are 7 friends, how many meeting places are needed? How about 8, or 9? It is speculated that with the addition of every 2 new friends that one new meeting place will be needed.
Q6: If one friend skips every month on a rotating basis, how does that change the number and location of meeting places? If there are six friends and five meeting every month, are there six meeting places needed, or can there be less (in the general case)?
Q7: If the conditions are relaxed that the distances traveled do not have to be exactly the same, but only within epsilon of each other, how do the approaches change? E.g. can a “best fit” ellipse be found that comes close to all the friends?
There are plenty of other questions… But I’m most interested in questions 2 and 2a – a good old fashion deterministic, solve these equations approach. I also find questions 3, 5 & 6 very interesting, but first things first – questions 2 & 2a.
Best regards,
Randy
