Finding k points with minimum diameter and related problems

Alok Aggarwal; Hiroshi Imai; Naoki Katoh; Subhash Suri

doi:10.1016/0196-6774(91)90022-Q

Journal of Algorithms

Paper

01 Jan 1991

Finding k points with minimum diameter and related problems

View publication

Abstract

Let S be a set consisting of n points in the plane. We consider the problem of finding k points of S that form a "small" set under some given measure, and present efficient algorithms for several natural measures including the diameter and the variance. © 1991.

Paper