A dynamic separator algorithm

Our work is based on the pioneering work in sphere separators of Miller, Teng, Vavasis et al, [8, 12], who gave efficient static algorithms for finding sphere separators of size s(n)=O(Formula Presented) for a set of points in Rd. We present randomized, dynamic algorithms to maintain separators and answer queries about a dynamically changing point set. Our algorithms maintain a separator in expected time O(log n) and maintain a separator tree in expected time O(log3n). This is the first known polylog dynamic algorithm for finding separators of a large class of graphs known as overlap graphs [12], which include planar graphs and k-neighborhood graphs. We also give a general technique for transforming a class of expected time randomized incremental algorithms that use random sampling into incremental algorithms with high likelihood time bounds. In particular, we show how we can maintain separators in time O(log3n) with high likelihood.

Duke Scholars

Author John H. Reif Computer Science