A Linear-Size Well-Separated Pair Decomposition for Unit Disk Graphs
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
- The Rhythm of the Tiles: Narrow and Low Temperature Computation and Simulation in Synchronous Tile Self-Assembly
- k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs
- Covering Points with Rectangular Boundaries
- Tiling 3D Space by (Translates of) a Single Polycube is Undecidable
- Quadratic Complexity of Voronoi Diagrams in R cubed for Lines in a Single Ruling of a Regulus
- Minimum central circles: chain order, seam obstructions, and exact finite certification