particular data structure similar to a kd-tree to decompose the problem into 2-dimensional components and aggregate those components efficiently; the 2-dimensional problems themselves are solved efficiently using a trellis structure. Although asymptotically faster than Bentley's algorithm, its data structures use significantly more space, so it is only used in problems where either n or d is large. In 1998, Bogdan Chlebus proposed a simpler algorithm with the same asymptotic running time for the common special cases where d is 3 or 4. In 2013, Timothy M. Chan developed a simpler algorithm that avoids the need for dynamic data structures and eliminates the logarithmic factor, lowering the best known running time for d ≥ 3 to . Known bounds The only known lower bound for any d is , and optimal algorithms with this running time are known for d=1 and d=2. The Chan algorithm provides an upper bound of for d ≥ 3, so for d ≥ 3, it remains an open question whether faster algorithms are possible, or alternatively whether tighter lower bounds can be proven. In particular, it remains open whether the algorithm's running time must depend on d. In addition, the question of whether there are faster algorithms that can deal with special cases (for example, when the input coordinates are integers within a bounded range) remains open. The 1D Klee's measure problem (union of intervals) can be solved in where p denotes the number of piercing points required to stab all intervals (the union of intervals pierced by a common point can be calculated in linear time by computing the extrema). Parameter p is an adaptive parameter that depends on the input configuration, and the piercing algorithm yields an adaptive algorithm for Klee's measure problem. See also Convex volume approximation, an efficient algorithm for convex bodies References and further reading Important papers . . . . . . . Secondary literature Franco P. Preparata and Michael I. Shamos (1985). Computational Geometry (Springer-Verlag, Berlin). Klee's Measure Problem, from Professor Jeff Erickson's list of open problems in computational geometry. (Accessed November 8, 2005, when the last update was July 31, 1998.) References Computational geometry Measure theory Mathematical problems