A dynamic separator algorithm

Conference Paper

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.

Full Text

Duke Authors

Cited Authors

  • Armon, D; Reif, J

Published Date

  • January 1, 1993

Published In

Volume / Issue

  • 709 LNCS /

Start / End Page

  • 108 - 118

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783540571551

Digital Object Identifier (DOI)

  • 10.1007/3-540-57155-8_240

Citation Source

  • Scopus