Dynamic point location in arrangements of hyperplanes

Abstract

We present algorithms for maintaining data structures supporting fast (polylogarithmic) point-location and ray-shooting queries in arrangements of hyperplanes. This data structure allows for deletion and insertion of hyperplanes. Our algorithms use random bits in the construction of the data structure but do not make any assumptions about the update sequence or the hyperplanes in the input. The query bound for our data structure is Õ(polylog(n)), wheren is the number of hyperplanes at any given time, and the Õ notation indicates that the bound holds with high probability, where the probability is solely with respect to randomization in the data structure. By high probability we mean that the probability of error is inversely proportional to a large degree polynomial inn. The space requirement is Õ(n^d). The cost of update is Ö(n^d−1 log n. The expected cost of update is O(n^d−1); the expectation is again solely with respect to randomization in the data structure. Our algorithm is extremely simple. We also give a related algorithm with optimal Õ(log n) query time, expected O(n ^d) space requirement, and amortized O(n^d−1) expected cost of update. Moreover, our approach has a versatile quality which is likely to have further applications to other dynamic algorithms. For d=2, 3 we also show how to obtain polylogarithmic update time in the CRCW PRAM model so that the processor-time product matches (within a polylogarithmic factor) the sequential update time.