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).

In reply to Re: Puzzle: The Ham Cheese Sandwich cut. by jeffguy
in thread Puzzle: The Ham Cheese Sandwich cut. by Perl Mouse

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.