Re: Puzzle: The Ham Cheese Sandwich cut.

Observation 1 (or maybe it's just obvious): For even numbers of points, there may be more than one correct answer (even aside from trivially jittering the dividing line back and forth a little). Example: two red points (0,0),(1,1) and two green points (1,0),(0,1). Plotting them:

g  r

r  g
[download]

They can be divided vertically or horizontally. Declaring an odd number of points of each color and requiring that no two points be at the same spot may force a unique solution, but I'm not sure. Wow! This is a tough problem!
Update: Turns out there are at least some graphs with an odd number of each color of node and where there are multiple correct answers.
Example:

Red:
1.581132197    0.614876988
6.762647456    6.783073022
1.712908647    0.607512624
1.162182053    0.915644789
3.323045845    5.339670711
6.579598161    6.786753061
3.361003489    5.865087821
2.875597765    5.736911416
7.422065511    6.614127605

Green:
4.982671611    5.227664832
5.171096225    5.290000579
1.615214988    7.190650026
5.008097411    6.200513048
5.565258291    5.446259215
4.654470193    5.099949178
5.093037705    6.804907981
5.348031291    4.568270604
4.787041271    4.655722514
[download]

One answer passes a line through the first red and the first green, another through the second red and second first green, and still another answer passes a line through the third red and second green!

Update: I have an n^2 algorithm (not implemented yet, but it works).

Comment on Re: Puzzle: The Ham Cheese Sandwich cut. Select or Download Code

Replies are listed 'Best First'.
Re^2: Puzzle: The Ham Cheese Sandwich cut. by Perl Mouse (Chaplain) on Nov 18, 2005 at 10:05 UTC
For even numbers of points, there may be more than one correct answer Indeed. That's why the puzzle says returns a line, and not returns the* line. `Perl --((8:>`	[reply]