Geometric Separators and the Parabolic Lift
Donald R. Sheehy · 2013
A geometric separator for a set U of n geometric ob-jects (usually balls) is a small (sublinear in n) subset whose removal disconnects the intersection graph of U into roughly equal sized parts. These separators provide a natural way to do divide and conquer in geometric set-tings. A particularly nice geometric separator algorithm originally introduced by Miller and Thurston has three steps: compute a centerpoint in a space of one dimen-sion higher than the input, compute a conformal trans-formation that “centers ” the centerpoint, and finally, use the computed transformation to sample a sphere in the original space. The output separator is the subset of S intersecting this sphere. It is both simple and ele-gant. We show that a change of perspective (literally)