Abstract
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(n3/2 log n) time with O(pn) 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 log2 n) time with O(log2 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 log3 n) time with O(log2 n) extra space.
Original language | English (US) |
---|---|
Pages | 27-30 |
Number of pages | 4 |
State | Published - 2005 |
Externally published | Yes |
Event | 17th Canadian Conference on Computational Geometry, CCCG 2005 - Windsor, Canada Duration: Aug 10 2005 → Aug 12 2005 |
Conference
Conference | 17th Canadian Conference on Computational Geometry, CCCG 2005 |
---|---|
Country/Territory | Canada |
City | Windsor |
Period | 8/10/05 → 8/12/05 |
ASJC Scopus subject areas
- Geometry and Topology
- Computational Mathematics