Talk:Range searching
 | This article has not yet been rated on Wikipedia's content assessment scale. |
acerb in the last paragraph seems like the wrong word. possibly the writer was German and was trying to say "beißend, ätzend," which seems kind of informal to me. Perhaps a formal equivalent would be primitive. If you want to be informal, then perhaps pitiful?
- Orthogonal Range Searching
Chazelle results also considers the general case of arbitrary constant dimension $d$. What is the result in this case? In the paper there are tables of results that seem to be about the complexity of the problem for $d=2$. After those tables, it says:
> Also for the sake of exposition, we restrict ourselves to two > dimensions ($d=2$), but we recall a classical technique (Bentley [B2]) that allows us > to extend all our data structures to $R^d$ ($d > 2$). To obtain the complexity of the resulting > algorithms, just multiply each expression in the original complexity by a factor of > $\log^{d-2} n$ (note: the terms involving k remain unchanged, but a term $\log^{d-1} n$ is to be > included in the query times). — Preceding unsigned comment added by Aureooms (talk • contribs) 13:26, 14 June 2019 (UTC)