Home Bookmarks Papers Blog

# On Clusters that are Separated but Large

$\newcommand{\spreadC}{\Mh{\Phi}}% \newcommand{\cpX}{\Mh{\mathrm{c{}p}}\pth{#1}}% \newcommand{\diamX}{\mathrm{diam}\pth{#1}}% \newcommand{\sep}{\Mh{\mathsf{s}}}% \newcommand{\PS}{\Mh{P}}% \newcommand{\kk}{\Mh{\mathsf{k}}}% \newcommand{\Re}{\mathbb{R}} \newcommand{\reals}{\mathbb{R}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\rad}{r} \newcommand{\Mh}{#1} \newcommand{\query}{q} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\IntRange}{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[\!]{#1\left({#2}\right)} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\distY}{\left\| {#1} - {#2} \right\|} \newcommand{\ptq}{q} \newcommand{\pts}{s}$
Sariel Har-Peled and Joseph Rogge.
Given a set $\PS$ of $n$ points in $\Re^d$, consider the problem of computing $\kk$ subsets of $\PS$ that form clusters that are well-separated from each other, and each of them is large (cardinality wise). We provide tight upper and lower bounds, and corresponding algorithms, on the quality of separation, and the size of the clusters that can be computed, as a function of $n,d,\kk,\sep$, and $\spreadC$, where $\sep$ is the desired separation, and $\spreadC = \diamX{\PS}/ \cpX{\PS}$ is the spread of the point set $\PS$, where $\diamX{\PS}$ is the diameter of $\PS$, and $\cpX{\PS}$ is its closest pair distance in $\PS$.
PDF. : arXiv.