An improved algorithm for computing the volume of the union of cubes

Journal Article

Let c be a set of n axis-aligned cubes in ℝ , and let u(c) denote the union of c. We present an algorithm that computes the volume of u(c) in time O(n polylog(n)). The previously best known algorithm takes O(n log n) time. 3 4/3 2

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK

Published Date

  • July 30, 2010

Published In

  • Proceedings of the Annual Symposium on Computational Geometry

Start / End Page

  • 230 - 239

Digital Object Identifier (DOI)

  • 10.1145/1810959.1811000

Citation Source

  • Scopus