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

Published

Journal Article

Let c be a set of n axis-aligned cubes in ℝ3, 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 4/3 log2 n) time.

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