## Abstract

We extend the classic notion of well-separated pair decomposition to the (weighted) unit-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 in the plane and for any constant c ≥ 1, there exists a c-well-separated pair decomposition with O(n log n) pairs, and the decomposition can be computed in O(n log n) time. We also show that for the unit-ball graph metric in k dimensions where k ≥ 3, there exists a c-well-separated pair decomposition with O(n^{2-2}/k) pairs, and the bound is tight in the worst case. We present the application of the well-separated pair decomposition in obtaining efficient algorithms for approximating the diameter, closest pair, nearest neighbor, center, median, and stretch factor, all under the unit-disk graph metric.

Original language | American English |
---|---|

Pages (from-to) | 483-492 |

Number of pages | 10 |

Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

DOIs | |

State | Published - 2003 |

Externally published | Yes |

Event | 35th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States Duration: Jun 9 2003 → Jun 11 2003 |

## ASJC Scopus subject areas

- Software

## Keywords

- Approximation algorithm
- Unit-disk graph
- Well separated pair decomposition