Geometric kernel diversity enables fast diverse point set measurement
Geometric Kernel Diversity: An Axiomatic Diversity Measure in Euclidean Space
Computational GeometryComputational ComplexityMachine Learning
Summary
Measuring how different a group of things is can be tricky. The paper looks at ways to measure this diversity for points in normal space that have to follow certain simple rules. The authors introduce a new method called Geometric Kernel Diversity that adds shapes around each point and measures their combined space to check diversity. This new method can be calculated quickly for small dimensions and can be approximated efficiently even when dimensions are higher. This work also shows that older methods remain very hard to compute, even with simple points.
What this means in practice
- •For machine learning engineers: Quickly measure diversity of feature point sets in low-dimensional spaces for model selection or clustering.
- •For data analytics teams: Efficiently approximate diversity of high-dimensional Euclidean data to improve statistical sampling or coverage analysis.
Authors
Ditbul Ban, Younghun Roh, Julian Shun, Vihan Lakshman
Abstract
Quantifying the diversity of a set of objects is a fundamental problem in machine learning and statistics. Mironov and Prokhorenkova (2025) recently showed that three axioms-monotonicity, uniqueness, and continuity-are crucial for a reliable diversity measure and that none of the standard metrics in the literature satisfy all three. They also constructed two measures that do satisfy the axioms, but both are NP-hard to compute, leaving open the question of whether efficient axiomatic diversity measures can exist. We study a Euclidean-restricted version of this question. We introduce Geometric Kernel Diversity (GKD), which associates a radial kernel solid with each point and measures the volume of their union. We show that canonical GKD satisfies all three Mironov-Prokhorenkova axioms on Euclidean-realizable inputs. For canonical GKD, we give exact polynomial-time algorithms in dimensions $d \le 3$. In arbitrary dimensions, we give a randomized algorithm that returns a $(1 \pm \varepsilon)$-approximation with probability at least $1-δ$ in time $O \left(\frac{nd}{\varepsilon^2}\log\frac{2}δ\right)$ for $n$ points. The axiomatic guarantee applies to exact canonical GKD; the randomized algorithm approximates this deterministic quantity. We further show that the two diversity measures of Mironov and Prokhorenkova (2025) remain NP-hard on Euclidean-realizable inputs and, unless $\mathrm{NP} = \mathrm{RP}$, admit no FPRAS even on this restricted domain.