Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
So in this math exchange question I asked, it was proven that for $n>2$ dimensions, you can always find a curve that separates $k$ points in $n$-dimensional space into $2$ arbitrary sets that you pre-defined. What I wanted to know is if there is a polytime algorithm (polynomial in $k$) for determining this curve.
If so, is there a known way to transform this curve into a function using some form of linear or non-linear transformation?
What I wanted to know is if there is a polytime algorithm (on the order of k) for determining this curve. If so, is there a known way to transform this curve into a function using some form of linear or non-linear transformation?
Yes, this is possible. The equation for the curve will be nonlinear. (It is not possible to have a linear equation which describes the curve, because there exists sets of $k$ points (as long as $k \ge 4$) where no linear separator exists.)
Let the $k$ points in $n \ge 3$ dimensions be $\vec{x}_1, \vec{x}_2, \ldots, \vec{x}_k \in \mathbb{R}^n$. For each point $\vec{x}_i$, suppose the set it is in is given by a label $\ell_i$, which is either $+1$ or $-1$. So the points are divided into those labeled $+1$ and those labeled $-1$.
Then we define the following function: \begin{align*} f: \mathbb{R}^n &\to \mathbb{R} \\ f(\vec{x}) &:= \sum_{i=1}^k \ell_i \cdot \exp \left(- \frac{\log k}{d_{min}} \|\vec{x} - \vec{x}_i\| \right), \end{align*} where $d_{min}$ is the minimum distance between a pair of points, over all pairs of $2$ out of the $k$ points. That is, we take the minimum over $\|\vec{x}_1 - \vec{x}_2\|$, $\|\vec{x}_1 - \vec{x}_3\|$, etc. I am using $\| \cdot \|$ to denote the norm, that is, the length of vectors in $\mathbb{R}^n$.
Now I claim that your desired curve is given by the set $$ \big\{ x \;\mid\; f(\vec{x}) = 0 \big\}. $$
To justify this, we should show that $f$ separates the points labeled $+1$ from those labeled $-1$. So we first calculate $f(\vec{x}_i)$. We get \begin{align*} f(\vec{x}_i) = \underbrace{\ell_i \cdot \exp \left(- \frac{\log k}{d_{min}} \|\vec{x} - \vec{x}_i\| \right)}_{= \ell_i \cdot e^0 = \ell_i} + \underbrace{\sum_{j \ne i} \ell_j \cdot \exp \left(- \frac{\log k}{d_{min}} \|\vec{x} - \vec{x}_j\| \right)}_{\text{small}} \end{align*} Now the first term is just $\ell_i$, which is $1$ or $-1$, and the second term is small enough that it doesn't change the sign. Specifically, we can bound the second term (in absolute value) by $$ (k-1) \exp \left( -\frac{\log k}{d_{min}} \cdot d_{min}\right) = (k-1) \cdot \frac{1}{k} < 1. $$
So $f$ is positive on points labeled $+1$ and negative on points labeled $-1$. Also, $f$ is continuous on the entire $\mathbb{R}^n$. So, the points $\vec{x}$ where $f(\vec{x}) = 0$ must be a separating boundary curve between the positively and the negatively labeled points. $\square$
Finally, some notes:
Definition of a curve: In the question, it is not defined what a curve is, here; I took it to be the zero set of a continuous function, but you might want something more specific. This curve is actually a $(k-1)$-dimensional surface, but it might not be smooth at the points $\vec{x}_i$. A modification could be made that would smooth out these points by replacing $\|\vec{x} - \vec{x}_i\|$ with $\|\vec{x} - \vec{x}_i\|^2$ and $d_{min}$ with $d_{min}^2$.
Polynomial time: Returning the function $f$ is polynomial time: the only hard part is to compute the quantity $d_{min}$, which requires computing the distance between every pair of points in the set. So this is $O(k^2)$ time. The rest is just $O(k)$ time. Note that this requires that we have a model of computation in mind where arithmetic can be done on real-number values (it won't be a traditional Turing machine).
I think that the proof in your provided link describes an algorithm that runs at $O(k^2\cdot n)$ time.
