An in-place algorithm for Klee's measure problem in two dimensions |
| |
Authors: | Jan Vahrenhold |
| |
Affiliation: | Universität Dortmund, Informatik XI, 44221 Dortmund, Germany |
| |
Abstract: | We present the first in-place algorithm for solving Klee's measure problem for a set of n axis-parallel rectangles in the plane. Our algorithm runs in O(n3/2logn) time and uses O(1) extra words in addition to the space needed for representing the input. The algorithm is surprisingly simple and thus very likely to yield an implementation that could be of practical interest. As a byproduct, we develop an optimal algorithm for solving Klee's measure problem for a set of n intervals; this algorithm runs in optimal time O(nlogn) and uses O(1) extra space. |
| |
Keywords: | Analysis of algorithms Computational geometry |
本文献已被 ScienceDirect 等数据库收录! |