COMPUTING A CENTERPOINT OF A FINITE PLANAR SET OF POINTS IN LINEAR-TIME

The notion of a centerpoint of a finite set of points in two and higher dimensions is a generalization of the concept of the median of a set of reals. In this paper we present a linear-time algorithm for computing a centerpoint of a set of n points in the plane, which is optimal compared with the O(n log(3)n) complexity of the previously best-known algorithm. We use suitable modifications of the ham-sandwich cut algorithm in [Me2] and the prune-and-search technique of Megiddo [Me1] to achieve this improvement.