patternMinor
Given $k$ points in $n$-dimensions, such that $n\geq3$, is there a polytime algorithm for finding a curve that splits them into 2 sets of points?
Viewed 0 times
suchcurvepolytimepointssplitsintosetsgeq3algorithmthat
Problem
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?
If so, is there a known way to transform this curve into a function using some form of linear or non-linear transformation?
Solution
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}
-
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).
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}
-
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).
Context
StackExchange Computer Science Q#96210, answer score: 3
Revisions (0)
No revisions yet.