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

Authors
JADHAV S MUKHOPADHYAY A
Citation
S. Jadhav et A. Mukhopadhyay, COMPUTING A CENTERPOINT OF A FINITE PLANAR SET OF POINTS IN LINEAR-TIME, Discrete & computational geometry, 12(3), 1994, pp. 291-312
Citations number
9
Categorie Soggetti
Computer Sciences, Special Topics","Mathematics, General","Computer Science Theory & Methods",Mathematics
Journal title
Discrete & computational geometry → ACNP
ISSN journal
01795376
Volume
12
Issue
3
Year of publication
1994
Pages
291 - 312
Database
ISI
SICI code
0179-5376(1994)12:3<291:CACOAF>2.0.ZU;2-B
Abstract
The notion of a centerpoint of a finite set of points in two and highe r 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 comput ing 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 algo rithm in [Me2] and the prune-and-search technique of Megiddo [Me1] to achieve this improvement.