Re: Puzzle: The Ham Cheese Sandwich cut.

[BrowserUk]

If I calculate the median point of both datasets, (using the minimised Euclidian distance method, 2D for now), I get two points, one for each set of colors. These rarely match up with any of the given points.

If I project the line through those two points, it appears to divide the dataset as required. Is this the correct approach?

[jeffguy]

I think you're suggesting take four medians: the median of the X coordinates of the reds, the median of the Y coordinates of the reds, and the same for the greens. I don't understand what you might be doing with minimised Euclidean distance, though. Mind explaining? Then maybe I can tell you if it's on track with my aproach (which is NOT yet O(n)).

[BrowserUk]

I think you're suggesting take four medians: the median of the X coordinates of the reds, the median of the Y coordinates of the reds, and the same for the greens.

No. The problem is defining (or understanding) what the median is for a 2D dataset (R²).

Think of 3 points in the form of an equilateral triangle with the lower edge parallel to the X axis.

+
|        x
|       . .
|      .   .
|     .     .
|   .         .
|  .           .
| x.............x
+-------------------

Whilst the top point is the median in the X axis (looking up). The bottom right point is the median if you are looking in from the top left. Equally it's the bottom left point, if you look in from top right. Which would be the "correct median" depends upon the relative positioning of the other set of three points; or more correctly, their median. And the above three points can be rotated through 0->120°, giving an infinite number of directions to view the dataset, (or transformations you could apply), in order to access the median.

Which I think means that the warm-up problem is an almost complete red herring!

As you cannot work out which direction to look in (or which transformation of the coordinate system to apply), to determine the median for this dataset, until you know the median of the other. And vice versa. You cannot use a 'sort and take the middle' or K'th ordered element approach to determining the median as you would use for an R¹ dataset; for an R² dataset. Nor for the higher dimensions.

That leads you, (led me?), to think about how to determine the median of a set of points in R², without reference to the other dataset. And that's when I found the Euclidian distance method.

The premise is that the median of a R² dataset is that point at which the sum of the Euclidian distances between that point and the points in the datast is minimised.

There are other methods, including the point that minimises the sum of the areas of the sets of triangles formed between that point and pairs of points of the dataset, but that seems much harder to calculate.

[jeffguy]

I considered such possibilities, but ruled them out. (But remember, I also said your "tree" approach wouldn't work ;-)

My approach works cleanly and easily for 2D, but it relies heavily on the fact that it's 2D -- I can't imagine a parallel approach working in 3D (which hasn't stopped me from trying!). It seems to me that your post with the spoiler included holds the answer. Just have to figure out how to apply it to this problem.

[Perl Mouse]

What you are looking for in the 2-d case is a line, what you are looking for in the 3-d case is a plane. More general, what you are looking for in the n-d case, is an (n-1) simplex.

So, in the three-point example you describe, any line that goes to any of the points, and intersects the line segment joining the other two points (a line going through two points is will do as well). Any other line will have at least two points either to the left, or to the right, and will not do. (Although I don't think the problem becomes significantly different if you relax the requirements and require that on either side of the line are at most ceil(n/2) points - it that case, any line intersecting the triangle of the three points will do).