Update: I should clarify - this is the problem I'm referring to:
Given n sets of 2n points (each) in n dimensions, is there a single hyperplane that bisects each set (i.e divides it into two sets of size n).
In 2D, the problem is to bisect two sets (the ham and the bread).
3 comments:
What's the exact problem statement you're considering? In the plane, Megiddo did it in linear time (JALG '85).
Good point. let me update the post.
AFAIK, both HAM-SANDWICH and NECKLACE-SPLITTING are in PPAD but not known to be PPAD-complete. Both these problems are mentioned in Papadimitriou's 1994 paper.
Post a Comment