AN EXPANDER-BASED APPROACH TO GEOMETRIC OPTIMIZATION

We present a new approach to problems in geometric optimization that a re traditionally solved using the parametric-searching technique of Me giddo [J. ACM, 30 (1983), pp. 852-865]. Our new approach is based on e xpander graphs and range-searching techniques. It is conceptually simp ler, has more explicit geometric flavor, and does not require parallel ization or randomization. In certain cases, our approach yields algori thms that are asymptotically Easter than those currently known (e.g., the second and third problems below) by incorporating into our (basic) technique a subtechnique that is equivalent to (though much more flex ible than) Cole's technique for speeding up parametric searching [J. A CM, 34 (1987), pp. 200-208]. We exemplify the technique on three main problems-the slope selection problem, the planar distance selection pr oblem, and the planar two-line center problem. For the first problem w e develop an O(n log(3) n) solution, which, although suboptimal, is ve ry simple. The other two problems are more typical examples of our app roach. Our solutions have running time O(n(4/3) log(2) n) and O(n(2) l og(4) n), respectively slightly better than the previous respective so lutions of [Agarwal et al., Algorithmica, 9 (1993), pp. 495-514], [Aga rwal and Sharir, Algorithmica, 11 (1994), pp. 185-195]. We also briefl y mention two other problems that can be solved efficiently by our tec hnique. In solving these problems, we also obtain some auxiliary resul ts concerning batched range searching, where the ranges are congruent discs or annuli. For example, we show that it is possible to compute d eterministically a compact representation of the set of all point-disc incidences among a set of n congruent discs and a set of m points in the plane in time O((m(2/3)n(2/3) + m + n) log n), again slightly bett er than what was previously known.