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 , 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.
Volume / Issue
Start / End Page
Electronic International Standard Serial Number (EISSN)
International Standard Serial Number (ISSN)
International Standard Book Number 13 (ISBN-13)
Digital Object Identifier (DOI)