Jie Xue

Near-Optimal Dynamic Data Structures for Maximum Depth and Klee's Measure of Boxes

This approach integrates a classic grid-based partition framework with a novel charging analysis that controls the cost of structure-sensitive offline routines within each cell, to perform a global aggregation of the update time, by circumventing the worst-case costs associated with individual cell updates.