On a multidimensional search technique and its application to the Euclidean one-centre problem. (English) Zbl 0613.68044

Dyer, M. E.

SIAM J. Comput. 15, 725-738 (1986).

The paper is divided into two main sections. The first deals with a multidimensional search technique of N. Megiddo [J. Assoc. Comput. Mach. 31, 114-127 (1984)], and suggests an improvement. The second gives an application of the technique to the Euclidean one-centre problem in \({\mathbb{R}}^ d\). An algorithm of time-complexity \(O(3^{(d+2)^ 2}n)\) is derived for this problem. This improves the best previous bound even in the case \(d=2\).

MSC:

68U99	Computing methodologies and applications
90C05	Linear programming
68Q25	Analysis of algorithms and problem complexity

Keywords:

linear time algorithms; computational geometry; location problems; multidimensional search; Euclidean one-centre problem