Publications [#329094] of John H. Reif

Conference articles PUBLISHED

1. Armon, D; Reif, J, A dynamic separator algorithm, Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, vol. 709 LNCS (January, 1993), pp. 108-118, ISBN 9783540571551 [doi]
   (last updated on 2026/01/15)

   Abstract:
   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 R^d. 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(log³n). 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(log³n) with high likelihood.