Efficient partition trees |
| |
Authors: | Ji?í Matou?ek |
| |
Institution: | (1) Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czechoslovakia |
| |
Abstract: | 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). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|