{"id":"arxiv/2611.24295","url":"https://arxiv.org/abs/2611.24295","tags":["cs.CG","math.CO"],"score":0,"title":"A Well-Separated Pair Decomposition of Linear Size for Unit-Disk Graphs","domain":"cs.CG","source":"arxiv","authors":["Mark de Berg","Joachim Gudmundsson","Sampson Wong"],"reviews":0,"subject":"cs.CG","summary":"We prove that every connected Euclidean-weighted unit-disk graph on $n$ vertices has a $(1/\\varepsilon)$-well-separated pair decomposition of size $O(n\\varepsilon^{-2}\\log(1/\\varepsilon))$. This resolves an open problem posed by Gao and Zhang in 2003. We also show that this bound is tight: there are connected unit-disk graphs for which any $(1/\\varepsilon)$-well-separated pair decomposition has size $Ω(n\\varepsilon^{-2}\\log (1/\\varepsilon))$.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-18","reactions":{}}