A Linear-Size Well-Separated Pair Decomposition for Unit Disk Graphs

arXiv:2611.22049 · cs.CG · Submitted 2026-11-17 · Read on arXiv

cs.CG

Submitted: 2026-11-17

Updated: 2026-11-17

Comments: 8 pages, 1 figure

License: http://creativecommons.org/licenses/by/4.0/

The gist: 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…

Abstract

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(n 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.

Related papers