A DETERMINISTIC LINEAR TIME ALGORITHM FOR GEOMETRIC SEPARATORS AND ITS APPLICATIONS

An O(kn+nlogn) time deterministic algorithm for computing the intersection graph of a k-ply neighborhood system and an O(nlogn) time algorithm for constructing a linear space, O(logn) query time search structure for a geometric query problem associated with k-ply neighborhood systems.