Intersection of unit-balls and diameter of a point set in R3

AbstractWe describe an algorithm for computing the intersection of n balls of equal radius in R3 which runs in time O(nlg2 n). The algorithm can be parallelized so that the comparisons that involve the radius of the balls are performed in O(lg3 n) batches. Using parametric search, these algorithms are used to obtain an algorithm for computing the diameter of a set of n points in R3 (the maximum distance between any pair) which runs in time O(n lg5 n). The algorithms are deterministic and elementary; this is in contrast with the running time O(nlgn) in both cases that can be achieved using randomization (Clarkson and Shor, 1989), and the running times O(nlg n) and O(nlg3 n) using deterministic geometric sampling (Brönnimann et al., 1993; Amato et al., 1994)