Geometric Separator for d-dimensional ball graphs
Kebin Wang, Shang‐Hua Teng · 2006
We study the graph partitioning problem on ddimensional ball graphs in a geometric way. Let B be a set of balls in d-dimensional Euclidean space with radius ratio ! and -precision. We prove that it can be partitioned into three sets BS,BI,BE such that the intersection of BI and BE is empty, and for some constant # , the volume of BI and BE is less than # portion of volume of B, and the volume of BS is of size O($ / ,(µ(B)) 1 d), where µ(B) is the volume of B. We also provide a randomized algorithm to find such a partition in linear time.