Given $k$ points in $n$-dimensional space, is there always a continuous $n-1$ surface that can divide the points into two arbitrary groups?

Question

Say we have $k$ points in set $P\mid x_i\in\mathbb{Z}^n$, such that $k=\mathcal{O}(n!)$. We now arbitrarily divide the points into two sets, $A$, $B$. Note that $A\cup B = P$ and $A \cap B = \varnothing$.

Is there always $n-1$ dimensional surface in $\mathbb{R}^n$ that perfectly separates these two sets of points? Is there some transformation $T:\mathbb{R^n}\rightarrow\mathbb{R^n}$, such that this $n-1$ dimensional surface is a function $f(\vec x)$? If so is it always possible to find this function?

I know this is similar to the idea of SVN machine learning, but I'm more interested in the theoretical ideas about existence of these divides.

Answer 1

As quasi pointed out, the condition $n\geq 2$ is necessary.

We use induction on $n$. The statement holds for $n=2$. Indeed, connect the points in one of the two sets, say $A$, to make a closed, simple curve (no self-intersection). Use segments connecting the points in an appropriate order to obtain such a curve. (We don't want any Peano nonsense.) If a point of $B$ happens to be on this curve, make a detour. Then create a tube around this curve: using segments parallel to the ones in the curve, very close to the curve on both sides. If you pick these parallel segments close enough, only points in $A$ are inside this closed tube. Then cut the tube by breaking one of the pipes and seal the ends. That is, pick a pair of segments perpendicular to the pipe connecting the two walls of the pipe, and delete the part of the two walls between the segments. Then the walls of the broken tube and the two seals together form a polyhedron that separates $A$ from $B$.

Now let $n>2$ and assume that the statement holds for $n-1$. There are finitely many points given, so there are finitely many (ordered) pairs of them. Each pair $(P,Q)$ specifies a vector: the vector $\overrightarrow{PQ}$. Pick a vector $\overrightarrow{v}$ that is not parallel to any of these, and let $H$ be the hyperplane ($(n-1)$-dimensional subspace) with normal vector $\overrightarrow{v}$. Project all the points onto $H$. Solve the problem in $H$ for the projected points (induction hypothesis): an $(n-2)$-dimensional surface $S$ does the job.
Then $S'= \{s+c\overrightarrow{v} \mid s\in S, c\in \mathbb{R}\}$ is a good solution for the original points.

Answer 2

Solve the poisson equation, $\Delta u = f$ with $f$ consisting of delta function sources at points in $A$ and sinks at points in $B$. The zero set of the solution $u$ separates the points. One should be able to prove that either this zero set is smooth, or the zero set associated with arbitrarily small perturbations of the points is smooth, by using elliptic regularity and Sard's theorem.

You could also compute the sensitivity of the surface to movement of the points with the implicit function theorem.

The surface may consist of several disconnected components though.