caa a22 4500 469074965 CHVBK 20180323132932.0 cr unu---uuuuu 170328e19920901xx s 000 0 eng 10.1007/BF02293052 doi (NATIONALLICENCE)springer-10.1007/BF02293052 Dynamic point location in arrangements of hyperplanes [Elektronische Daten] [Ketan Mulmuley, Sandeep Sen] 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 logn. The expected cost of update isO(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Õ(logn) query time, expectedO(n d) space requirement, and amortizedO(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. Ford=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. Springer-Verlag New York Inc., 1992 Mulmuley Ketan Computer Science Department, University of Chicago, 60637, Chicago, IL, USA aut Sen Sandeep I.I.T., Delhi, India aut Discrete & Computational Geometry Springer New York 8/3(1992-09-01), 335-360 0179-5376 8:3<335 1992 8 454 https://doi.org/10.1007/BF02293052 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02293052 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Mulmuley Ketan Computer Science Department, University of Chicago, 60637, Chicago, IL, USA aut NATIONALLICENCE 700 1- Sen Sandeep I.I.T., Delhi, India aut NATIONALLICENCE 773 0- Discrete & Computational Geometry Springer New York 8/3(1992-09-01), 335-360 0179-5376 8:3<335 1992 8 454 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer