Polytope kernel density estimates on Delaunay graphs

We present a polytope-kernel density estimation (PKDE) methodology that allows us to perform exact mean-shift up dates along the edges of the Delaunay graph of the data. We discuss explicit and implicit constructions of such a PKDE, where in the implicit construction one can exploit a smoother kernel such as the standard isotropic Gaussian. The resulting density estimate allows us to perform mean-shift clustering in a computationally efficient manner (similar to mediod shift), but in a manner that is exact and consistent with the underlying density assumption. The procedure also yields a hierarchical connectivity structure, a tree, that spans the dataset. We demonstrate how this tree, combined with density-weighted geodesic distance calculations between modal samples can be used to select number of clusters as well as a distance preserving dimension reduction technique.