A (slightly) faster algorithm for Klee's measure problem

P.K. Agarwal, H. Kaplan, M. Sharir, Computing the volume of the union of cubes, in: Proc. 23rd ACM Sympos. Comput. Geom., 2007, pp. 294–301 Baran, 2008, Subquadratic algorithms for 3SUM, Algorithmica, 50, 584, 10.1007/s00453-007-9036-3 M. Ben-Or, Lower bounds for algebraic computation trees, in: Proc. 15th ACM Sympos. Theory Comput., 1983, pp. 80–86 J.L. Bentley, Algorithms for Klee's rectangle problem, unpublished manuscript, 1977 Boissonnat, 1998, Voronoi diagrams in higher dimensions under certain polyhedral distance functions, Discrete Comput. Geom., 19, 473, 10.1007/PL00009366 Cabello, 2008, On the parametrized complexity of d-dimensional point set pattern matching, Inform. Process. Lett., 105, 73, 10.1016/j.ipl.2007.08.003 S. Cabello, P. Giannopoulos, C. Knauer, D. Marx, G. Rote, Geometric clustering: Fixed-parameter tractability and lower bounds with respect to the dimension, in: Proc. 19th ACM–SIAM Sympos. Discrete Algorithms, 2008, pp. 836–843 Chan, 1999, Geometric applications of a randomized optimization technique, Discrete Comput. Geom., 22, 547, 10.1007/PL00009478 Chan, 2003, Semi-online maintenance of geometric optima and measures, SIAM J. Comput., 32, 700, 10.1137/S0097539702404389 T.M. Chan, More algorithms for all-pairs shortest paths in weighted graphs, in: Proc. 39th ACM Sympos. Theory Comput., 2007, pp. 590–598 Chew, 1999, Geometric pattern matching in d-dimensional space, Discrete Comput. Geom., 21, 257, 10.1007/PL00009420 Datta, 1995, Static and dynamic algorithms for k-point clustering problems, J. Algorithms, 19, 474, 10.1006/jagm.1995.1048 Dietz, 1989, Optimal algorithms for list indexing and subset rank, vol. 382, 39 Dobkin, 1996, Computing the discrepancy with applications to supersampling patterns, ACM Trans. Graph., 15, 354, 10.1145/234535.234536 Dumitrescu, 2004, Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles, Discrete Comput. Geom., 31, 207, 10.1007/s00454-003-0729-3 Eppstein, 1994, Iterated nearest neighbors and finding minimal polytopes, Discrete Comput. Geom., 11, 321, 10.1007/BF02574012 D. Eppstein, S. Muthukrishnan, Internet packet filter management and rectangle geometry, in: Proc. 12th ACM–SIAM Sympos. Discrete Algorithms, 2001, pp. 827–835 Erickson Frandsen, 2001, Lower bounds for dynamic algebraic problems, Inf. Comput., 171, 333, 10.1006/inco.2001.3046 Fredman, 1978, The complexity of computing the measure of ⋃[ai,bi], Commun. ACM, 21, 540, 10.1145/359545.359553 S. Har-Peled, V. Koltun, D. Song, K.Y. Goldberg, Efficient algorithms for shared camera control, in: Proc. 19th ACM Sympos. Comput. Geom., 2003, pp. 68–77 H. Kaplan, N. Rubin, M. Sharir, E. Verbin, Counting colors in boxes, in: Proc. 18th ACM–SIAM Sympos. Discrete Algorithms, 2007, pp. 785–794 Klee, 1977, Can the measure of ⋃1n[ai,bi] be computed in less than O(nlogn) steps?, Amer. Math. Monthly, 84, 284, 10.2307/2318871 van Leeuwen, 1981, The measure problem for rectangular ranges in d-space, J. Algorithms, 2, 282, 10.1016/0196-6774(81)90027-4 Matoušek, 1992, Efficient partition trees, Discrete Comput. Geom., 8, 315, 10.1007/BF02293051 Matoušek, 1992, Reporting points in halfspaces, Comput. Geom. Theory Appl., 2, 169, 10.1016/0925-7721(92)90006-E Matoušek, 1993, Range searching with efficient hierarchical cuttings, Discrete Comput. Geom., 10, 157, 10.1007/BF02573972 Nesetril, 1985, On the complexity of the subgraph problem, Comment. Math. Univ. Carol., 26, 415 Overmars, 1991, New upper bounds in Klee's measure problem, SIAM J. Comput., 20, 1034, 10.1137/0220065 Reif, 1997, On dynamic algorithms for algebraic problems, J. Algorithms, 22, 347, 10.1006/jagm.1995.0807