Publisher's Synopsis
Excerpt from The Volume of the Union of Many Spheres and Point Inclusion Problems
The problem of estimating the area of the union of many circles in the plane was first posed by [shamos, It is straightforward to solve this problem by an 0(n2) time deterministic algorithm. We show here how to use Monte Carlo techniques (developed by [karp, Luby, 83] for estimation of the failure probability of an n-component system) to get an 0(n) probabilistic algorithm.. This algorithm can trivially be extended to compute the volume of the union of n spheres (or boxes, or any collection of n fixed description objects) in k dimensions, in time o(nk). The accuracy of the algorithm is controlled by the algorithm implementer. Its running time is optimal in the sense that 0(n) time is needed to compute the sum of n real-numbers, under quite general models of computation. An application of this algorithm is a probabilistic 0(n) time method to test if n 'given spheres have a nonzero measure intersection. This can also be extended to test for intersections in k dimensions. No efficient algorithms for the problem of computing volumes of unions of objects in more than two dimensions were presented in the past. The fastest up to now algorithm for testing if n spheres intersect was invented by [schwartz, Hopcroft, Sharir, 83] and runs in time 0(n This algorithm detects also zero measure intersections. About the Publisher Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.
