Computing a centerpoint of a finite planar set of points in linear time |
| |
Authors: | S Jadhav A Mukhopadhyay |
| |
Institution: | (1) Department of Computer Science, Indian Institute of Technology, Kanpur, India |
| |
Abstract: | 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 ofn points in the plane, which is optimal compared with theO(n log3
n) complexity of the previously best-known algorithm. We use suitable modifications of the hamsandwich cut algorithm in Me2]
and the prune-and-search technique of Megiddo Me1] to achieve this improvement. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|