Answers are grounded in this paper and cite their sources.
Given a metric space $(X, d)$ a c-well separated pair decomposition (WSPD) is a collection of `dumbbell' pairs of subsets $(A, B)$, A, B⊆ X, where the distance between the two sets is at least c times the diameter of each set and every pair of points in X is covered by one such pair. It is known that for a weighted unit disk graph metric of n points, there is a WSPD of size O(nlog n). But it is open whether this bound can be improved to $O(n)$. In this note, we answer this question affirmatively and provide an algorithm that yields a linear-size WSPD for unit disk graphs.
No takes yet. Share an insight, caveat, or question.
Jie Gao (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: