Space-efficient algorithms for klee's measure problem

Eric Y. Chen, Timothy M. Chan

Research output: Contribution to conferencePaperpeer-review

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 languageEnglish (US)
Pages27-30
Number of pages4
StatePublished - 2005
Externally publishedYes
Event17th Canadian Conference on Computational Geometry, CCCG 2005 - Windsor, Canada
Duration: Aug 10 2005Aug 12 2005

Conference

Conference17th Canadian Conference on Computational Geometry, CCCG 2005
Country/TerritoryCanada
CityWindsor
Period8/10/058/12/05

ASJC Scopus subject areas

  • Geometry and Topology
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Space-efficient algorithms for klee's measure problem'. Together they form a unique fingerprint.

Cite this