Math @ Duke

Publications [#235494] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Kaplan, H; Sharir, M, Computing the volume of the union of cubes,
Proceedings of the Annual Symposium on Computational Geometry
(2007),
pp. 294301 [doi]
(last updated on 2018/07/21)
Abstract: Let C be a set of n axisaligned cubes in R 3, and let U(C) denote the union of C. We present an algorithmthat can compute the volume of U(C) in time O(n 4/3 log n). The previously best known algorithm, by Overmars and Yap, computes the volume of the union ofany n axisaligned boxes in R 3 in O(n 3/2log n) time. Copyright 2007 ACM.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

