### Abstract

New upper bounds are given for the measure problem of V. Klee (1977) that significantly improve the previous bounds for dimensions greater than 2. An O(n^{d2} log n, n) time-space upper bound to compute the measure of a set of n boxes in Euclidean d-space is obtained. The solution requires several novel ideas including application of the inclusion/exclusion principle, the concept of trellises, streaming, and a partition of d-space.

Original language | English (US) |
---|---|

Title of host publication | Annual Symposium on Foundations of Computer Science (Proceedings) |

Publisher | Publ by IEEE |

Pages | 550-556 |

Number of pages | 7 |

ISBN (Print) | 0818608773, 9780818608773 |

DOIs | |

State | Published - 1988 |

### Publication series

Name | Annual Symposium on Foundations of Computer Science (Proceedings) |
---|---|

ISSN (Print) | 0272-5428 |

### ASJC Scopus subject areas

- Hardware and Architecture

## Cite this

Overmars, M. H., & Yap, C. K. (1988). New upper bounds in Klee's measure problem. In

*Annual Symposium on Foundations of Computer Science (Proceedings)*(pp. 550-556). (Annual Symposium on Foundations of Computer Science (Proceedings)). Publ by IEEE. https://doi.org/10.1109/sfcs.1988.21971