### Abstract

Given n axis-parallel boxes in a fixed dimension d≥3, how efficiently can we compute the volume of the union? This standard problem in computational geometry, commonly referred to as Klee's measure problem, can be solved in time O(nd/ ^{2}logn) by an algorithm of Overmars and Yap (FOCS 1988). We give the first (albeit small) improvement: our new algorithm runs in time nd/ ^{2}2 ^{O}( ^{log}n), where ^{log} denotes the iterated logarithm. For the related problem of computing the depth in an arrangement of n boxes, we further improve the time bound to near O(nd/ ^{2}/logd/ ^{2-1}n), ignoring loglogn factors. Other applications and lower-bound possibilities are discussed. The ideas behind the improved algorithms are simple.

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

Pages (from-to) | 243-250 |

Number of pages | 8 |

Journal | Computational Geometry: Theory and Applications |

Volume | 43 |

Issue number | 3 |

DOIs | |

State | Published - Apr 1 2010 |

### Fingerprint

### Keywords

- Boxes
- Data structures
- Union of geometric objects
- Volume

### ASJC Scopus subject areas

- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics