  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
$\mathbb{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
(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.
