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