A DETERMINISTIC LINEAR TIME ALGORITHM FOR GEOMETRIC SEPARATORS AND ITS APPLICATIONS

We give a deterministic linear time algorithm for finding a “good” sphere separator of a k-ply neighborhood system Φ in any fixed dimension, where a k-ply neighborhood system in $\IR$ d is a collection of n balls such that no points in the space is c