A Discrete and Dynamic Version of Klee’s Measure Problem

Given a set of axis-aligned boxes B = {B1, B2,..., Bn} and a set of points P = {p1, p2,..., pm} in d-space, let the discrete measure of B with respect to P be defined as meas(B,P) = |P ∩ {⋃ni=1Bi}|, namely, the number of points of P contained in the union of boxes of B. This is a discrete and dynamic version of Klee’s measure problem, which asks for the Euclidean volume of a union of boxes. Our result is a data structure for maintaining meas(B,P) under dynamic updates to both P and B, with O(logd n + m1− 1 d) time for each insert or delete operation in B, O(logd n + logm) time for each insert and O(logm) time for each delete operation in P, and O(1) time for the measure query. Our bound is slightly better than what can be achieved by applying a more general technique of Chan [3], but the primary appeal is that the method is simpler and more direct.