The Volume of the Union of Many Sheres and Point Inclusion Problems

Paul G. SpirakisSTACS 1985 · OpenReview

Abstract

We present here an O(n) probabilistic algorithm for computing the volume of the union of n spheres of possibly different radii. The method, which is an application of techniques developed by [Karp, Luby, 83], can be extended, in a straightforward manner, to compute the volume of the union of n objects (where each of them has an easy description e.g. boxes or spheres) in k dimensions. Its time complexity is then O(nk). We also examine the related problem of computing the number of spheres (or disks, in the plane) among a given set of spheres, containing a given point. For the case of n disks of the same radius r, we can answer such a query in time O(log2n) and O(n3) preprocessing space.
BibTeX
@inproceedings{spirakis1985volume,
  author = {Paul G. Spirakis},
  title = {{The Volume of the Union of Many Sheres and Point Inclusion Problems}},
  booktitle = {STACS},
  year = {1985},
  url = {https://openreview.net/forum?id=ix6KBmxBXA},
}

Loading related content...

Figure