5
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

I think that the proof in your provided link describes an algorithm that runs at $O(k^2\cdot n)$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.