Space-Efficient Algorithms for Klee's Measure Problem.
Eric Chen, Timothy M. Chan · Canadian Conference on Computational Geometry · 2005
We give space-efficient geometric algorithms for three related problems. Given a set of n axis-aligned rectangles in the plane, we calculate the area covered by the union of these rectangles (Klee’s measure problem) in O(n log n) time with O( √ n) extra space. If the input can be destroyed and there are no degenerate cases and input coordinates are all integers, we can solve Klee’s measure problem in O(n log n) time with O(log n) extra space. Given a set of n points in the plane, we find the axis-aligned unit square that covers the maximum number of points in O(n log n) time with O(log n) extra space.