Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications
Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications
We extend the classic notion of well-separated pair decomposition [P. B. Callahan and S. R. Kosaraju, J. ACM, 42 (1975), pp. 67--90] to theunit-disk graph metric: the shortest path distance metric induced by the intersection graph of unit disks. We show that for the unit-disk graph metric of n points …