Home Bookmarks Papers Blog

On Clusters that are Separated but Large

$ \newcommand{\spreadC}{\Mh{\Phi}}% \newcommand{\cpX}[1]{\Mh{\mathrm{c{}p}}\pth{#1}}% \newcommand{\diamX}[1]{\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]{#1} \newcommand{\query}{q} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\IntRange}[1]{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[2][\!]{#1\left({#2}\right)} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\distY}[2]{\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.
Last modified: Wed 2022-07-20 18:31:11 UTC 2022 by Sariel Har-Peled