Gao, Jie and Zhang, Li (2005) WellSeparated Pair Decomposition for the UnitDisk Graph Metric and Its Applications. SIAM Journal on Computing, 35 (1). pp. 151169. ISSN 00975397. http://resolver.caltech.edu/CaltechAUTHORS:GAOsiamjc05

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 wellseparated pair decomposition [P. B. Callahan and S. R. Kosaraju, J. ACM, 42 (1975), pp. 6790] to the unitdisk graph metric: the shortest path distance metric induced by the intersection graph of unit disks. We show that for the unitdisk graph metric of n points in the plane and for any constant $c\geq 1$, there exists a cwellseparated 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 unitball graph metric in k dimensions where $k\geq 3$, there exists a cwellseparated pair decomposition with O(n22/k) pairs, and the bound is tight in the worst case. We present the application of the wellseparated pair decomposition in obtaining efficient algorithms for approximating the diameter, closest pair, nearest neighbor, center, median, and stretch factor, all under the unitdisk 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:  wellseparated pair decomposition, unitdisk 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