Steinhaus' Geometric Location Problem for Random Samples in the Plane

摘要

The work of H. Steinhaus was apparently the first explicit treatment of the natural question 'How should one choose n points from a mass distributed in the plane so as to best represent the whole. The main objective of this article is to treat a stochastic analogue of Steinhaus' problem. One principle motivation for this stochastic analogue comes from developments in the theory of algorithms. The first of these is the discovery of Karp of an efficient probabilistic algorithm for solving the traveling salesman problem. The second development was the proof of Papadimitriou of the conjecture of Fisher and Hochbaum that the 'Euclidean k-median location problem' is NP-complete.