ISSN:
1439-6912
Keywords:
68 C 25
;
52 A 22
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract The combination of divide-and-conquer and random sampling has proven very effective in the design of fast geometric algorithms. A flurry of efficient probabilistic algorithms have been recently discovered, based on this happy marriage. We show that all those algorithms can be derandomized with only polynomial overhead. In the process we establish results of independent interest concerning the covering of hypergraphs and we improve on various probabilistic bounds in geometric complexity. For example, givenn hyperplanes ind-space and any integerr large enough, we show how to compute, in polynomial time, a simplicial packing of sizeO(r d ) which coversd-space, each of whose simplices intersectsO(n/r) hyperplanes.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02122778
