New applications of random sampling in computational geometry (Q1820582)

For a set \(X\) and integer \(i\), let \(X^i\) be the set of \(i\)-tuples of \(X\). For a positive integer \(n\), let \(\mathfrak n\) denote the set of integers \(\{1,2,\ldots,n\}\). Let \(b(j;t,\alpha)\) be the probability of \(j\) successes out of \(t\) Bernoulli trials with probability of success \(\alpha\). For region \(A\) and for \(B\) a set of regions (subsets) of \(E^d\), let \(\#(A,B)\) be the number of elements of \(B\) that have nonempty intersection with \(A\). The following theorems are proved: Theorem 1: Let \(S\) and \(\mathfrak F\) be sets of regions of \(E^d\) with \( |S| = s\). For fixed positive integers \(i\) and \(n\), let \(\nu_k\), \(k\in\mathfrak n\), be a collection of mappings from \(S^i\) to \(\mathfrak F\). Let \(R\) be a random sample of \(S\), of size \(r\), and let \(\mathfrak F_R\) be \(\{\nu_k(R^*)\); \(k\in\mathfrak n\), \(R^*\in R^i\}\) the union of the images of \(R^i\) under the \(\nu_k\)'s. Then for integer \(m\) and \(\alpha\in [0,1]\), with \(m\le (r-i)\alpha\), \[ \operatorname{Prob}\{\exists A\in\mathfrak F_ R \text{ with } \#(A,R)\le m\text{ and }\#(A,S)>\alpha s\}\le O(r^i)\sum_{j\le m}b(j;r-i,\alpha) \] as \(r\to \infty\). Similarly, for integer \(m\) and \(\alpha\in [0,1]\) with \(m\ge (r-i)\alpha\), \[ \operatorname{Prob}\{\exists A\in\mathfrak F_ R \text{ with } \#(A,R)\ge m\text{ and } \#(A,S)<\alpha s\}\le O(r^i)\sum_{j\ge m}b(j;r-i,\alpha) \] as \(r\to \infty\). When \(m\) is much larger than the mean \(\alpha r\), with high probability, every \(\#(A,R)\) is a good estimate of \(\#(A,S)\). A \(k\)-set of a set of sites (points) \(S\) in \(E^d\) is a subset of \(S\) of size \(k\) that is all on one side of some hyperplane, while the other sites are all on the other side of the hyperplane. Theorem 2: Let \(g_{k,3}(s)\) be the maximum total number of \((\le k)\)-sets of any set of \(s\) sites in \(E^3\). Then \[ g_{k,3}(s) = O(sk^2 \log^8s/(\log \log s)^6) \] \[ \text{(conjecture}\quad g_{k,d}(s) = O(s^{[d/2]}k^{[d/2]})). \] Theorem 3: One new algorithm is given for searching an arrangement of \(s\) hyperplanes in \(E^d\) in \(O(s^{d+\varepsilon})\) expected time and \(O(s^{d+\varepsilon})\) worst-case space, so that queries may be answered in \(O(\log s)\) time, as \(s\to \infty\), for fixed \(d\) and for any fixed \(\varepsilon >0\). Theorem 4: The separation of two polytopes \(A,B\subset E^d\) (minimum distance from a point of one to a point of the other) may be computed in expected time \(O((\vert A)^{[d/2]}+(\vert B)^{[d/2]})\) where \(\vert = \) number of vertices and the expectation is with respect to the random behavior of the algorithm. Several lemmas preceding the theorems are interesting by themselves.