| The Well-Separated Pair Decomposition has been widely used for solving proximity problems in Euclidean space. Theoretically, it can be extended to any metric space. But in fact, only few work has been done on such extensions. We extend the classic well-separated pair decomposition to the robust class of doubling metric spaces. We present a deterministic algorithm that constructs a Well-Separated Pair Decomposition in any doubling metric space. The number of pairs in this decomposition is O(n log Delta), where n is the number of elements and Delta is the aspect ratio of the metric space. |
