An Efficient Multi-Dimensional Searching Technique and itsApplications
K P Agarwal, Micha Sharir, Sivan Toledo · 1993
This paper describes an improved algorithm for the multi-dimensional searching problem introduced by Megiddo. As a result, we obtain a d O(d) n time deterministic algorithms for linear programming in R d with n constraints, for computing the Euclidean 1-center of a set of n points in R d , for computing the minimum enclosing ellipsoid of a set of n points in R d , etc. Our techniques also improve the running time of known algorithms for a number of parametric graph searching problems, including that of finding zero cycles in dynamic graphs [7].