We consider the following problem, known as simplex range searching: Preprocess a set P of n points in ~d SO that, given any query simplex q, the points in P n q can be counted or r e p o r t e d efficiently. We can put the m a n y variants of this problem under the same umbrella by assuming a weight function on the points and asking for the cumulative weight of the points in P N q. For the sake of generality, it is best to disallow the use of subtraction (which will make our upper bounds more powerful): formally, this means choosing weights in an additive semigroup.Our approach is broken up into three stages: We begin by investigating algorithms with polylogarithmic query time and polynomial-size d a t a structures. We show how to achieve O(log d+l n) query time at the expense of O(n dรท~) storage, for any e > 0. This result generalizes the two-dimensional solution of Paterson and Yao to higher dimensions at the expense of some e x t r a storage. It is used as a subroutine by the main algorithm, which we discuss in a second stage. This algorithm provides us with a family of tradeoffs in any fixed dimension. ~re show that with O(m) storage (n < m < n d) it is possible to answer any query in O(nl+e/ml/d) query time after O(m ~+~) preprocessing. This bound, which holds on a RAM or a pointer machine, is almost optimal: indeed, it comes very close to Chazelle's lower bound of ~((n/log n)/m ~/d) . It is actually the only tradeoff of this kind for a r b i t r a r y dimensions. T h e two-dimensional case, however, has already been solved almost optimally . Even for the special case where m is linear or quasi-linear, our result improves on previous solutions in dimension greater than 3 (Hanssler and Welzl [20], Yao and Yao [27]). Because of the extra n ~ factor, however, it falls slightly short of the solutions given by Chazelle and Welzl . But on the other hand, except in two and three dimensions, the upper bounds in hold only in the arithmetic model whereas our results hold on any general-purpose computer. See also for previous related work.Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission.