  We investigate the problem of exact cluster recovery using oracle queries.
Previous results show that clusters in Euclidean spaces that are convex and
separated with a margin can be reconstructed exactly using only $O(\log n)$
same-cluster queries, where $n$ is the number of input points. In this work, we
study this problem in the more challenging non-convex setting. We introduce a
structural characterization of clusters, called $(\beta,\gamma)$-convexity,
that can be applied to any finite set of points equipped with a metric (or even
a semimetric, as the triangle inequality is not needed). Using
$(\beta,\gamma)$-convexity, we can translate natural density properties of
clusters (which include, for instance, clusters that are strongly non-convex in
$R^d$) into a graph-theoretic notion of convexity. By exploiting this convexity
notion, we design a deterministic algorithm that recovers
$(\beta,\gamma)$-convex clusters using $O(k^2 \log n + k^2
(\frac{6}{\beta\gamma})^{dens(X)})$ same-cluster queries, where $k$ is the
number of clusters and $dens(X)$ is the density dimension of the semimetric. We
show that an exponential dependence on the density dimension is necessary, and
we also show that, if we are allowed to make $O(k^2 + k \log n)$ additional
queries to a "cluster separation" oracle, then we can recover clusters that
have different and arbitrary scales, even when the scale of each cluster is
unknown.
