The Volume of the Union of Many Sheres and Point Inclusion Problems
Lists
Only you see this
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...