Checking whether a set of points in the plane can be bi-partitioned with a certain diameter

Question

I am working on a problem in geometry and I encounter the following problem.

Suppose given $n=2k$ points $P$ in the plane. And we want partition points into two group

Is there an algorithm that decides whether we can $P$ into two groups the size of each group be exactly $k$ and diameter of each group be at most given input $d$? I try to use Linear separability but I get stuck.

Answer 1

Your problem may be mapped into graph partitioning algorithm. There you can use spectral graph partitioning algorithm.

---

I am just giving you brief here. What spectral graph partitioning does is:

1. First you calculate the adjacent matrix($W_(ij)$) basis on connectivity of your points.
2. From $W_(ij)$ calculate Degree Matrix(D). It is a kind of matrix where only diagonal elements are nonzero and those diagonal entry are the rowsum.
3. Then find Laplacian Matrix $L$ =$D$ - $W$

Now there are many things to understand how can be this turned into a optimization problem.

Basically our aim to establish a weak relationship between two clusters(in your case) whose equation is R = $w_(ij) * (f_i - f_j)^2$ where $f$ is the labelling column matrix in your case f consists only of $0$ and $1$.

So our aim is to minimize this R. This R can be mapped to $f^TLf$. So if we are able to determine that $f$ for which $f^TLf$ this minimizes our work will be done.

ONE particular lemma is there by Courant-fisher The second smallest eigen value is the minimum of $f^TLf$ for any $f$ belongs to $R$ subject to condition that $f^Tf = 1$. Taking Lagrange Multiplier as,

$La_r(x,\lambda)$ = The $fun^c$ we want to optimize - $\lambda$(equality constraint)

$La_r(x,\lambda)$ = $f^TLf$ - $\lambda(f^Tf -1)$

If you now perform derivative to this expression wrt $f$ then u will get as

$Lf = \lambda f$ ... familiar with this right.

Now the vector($f$) corresponding to the smallest eigen value($\lambda$) is your labelling vector

Points to be noted 1 eigen value allows you to bipartition of the graph. If you have k clusters have to take k smallest eigen value. Now there is another theorem which tells If the graph has k connected components L has k eigenvectors with $\lambda = 0 $. So if you take smallest eigen value which is 0 that will be of no use because the eigen vector corresponding to that value will be constant only. Start from 2nd one if you have 1 connected graph.

For more info: A tutorial upon Spectral

Time complexity