CaltechAUTHORS
  A Caltech Library Service

Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications

Gao, Jie and Zhang, Li (2005) Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications. SIAM Journal on Computing, 35 (1). pp. 151-169. ISSN 0097-5397. http://resolver.caltech.edu/CaltechAUTHORS:GAOsiamjc05

[img]
Preview
PDF
See Usage Policy.

234Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:GAOsiamjc05

Abstract

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 the 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\geq 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\geq 3$, there exists a c-well-separated pair decomposition with O(n2-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.


Item Type:Article
Additional Information:© 2005 Society for Industrial and Applied Mathematics. Reprinted with permission. Received by the editors October 16, 2003; accepted for publication (in revised form) February 2, 2005; published electronically October 3, 2005.
Subject Keywords:well-separated pair decomposition, unit-disk graph, approximation algorithm
Record Number:CaltechAUTHORS:GAOsiamjc05
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:GAOsiamjc05
Alternative URL:http://dx.doi.org/10.1137/S0097539703436357
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1370
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:12 Jan 2006
Last Modified:26 Dec 2012 08:44

Repository Staff Only: item control page