caa a22 4500 469074981 CHVBK 20180323132932.0 cr unu---uuuuu 170328e19920901xx s 000 0 eng 10.1007/BF02293051 doi (NATIONALLICENCE)springer-10.1007/BF02293051 Matoušek Jiří Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00, Praha 1, Czechoslovakia aut Efficient partition trees [Elektronische Daten] [Jiří Matoušek] We prove a theorem on partitioning point sets inE d (d fixed) and give an efficient construction of partition trees based on it. This yields a simplex range searching structure with linear space,O(n logn) deterministic preprocessing time, andO(n 1−1/d (logn) O(1)) query time. WithO(nlogn) preprocessing time, where δ is an arbitrary positive constant, a more complicated data structure yields query timeO(n 1−1/d (log logn) O(1)). This attains the lower bounds due to Chazelle [C1] up to polylogarithmic factors, improving and simplifying previous results of Chazelleet al. [CSW]. The partition result implies that, forr d≤n 1−δ, a (1/r)-approximation of sizeO(r d) with respect to simplices for ann-point set inE d can be computed inO(n logr) deterministic time. A (1/r)-cutting of sizeO(r d) for a collection ofn hyperplanes inE d can be computed inO(n logr) deterministic time, provided thatr≤n 1/(2d−1). Springer-Verlag New York Inc., 1992 Discrete & Computational Geometry Springer New York 8/3(1992-09-01), 315-334 0179-5376 8:3<315 1992 8 454 https://doi.org/10.1007/BF02293051 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02293051 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Matoušek Jiří Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00, Praha 1, Czechoslovakia aut NATIONALLICENCE 773 0- Discrete & Computational Geometry Springer New York 8/3(1992-09-01), 315-334 0179-5376 8:3<315 1992 8 454 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer