Selecting Points that are Heavily Covered by Pseudo-Circles, Spheres or Rectangles
Shakhar Smorodinsky, Micha Sharir · Combinatorics Probability Computing · 2004
In this paper we prove several point selection theorems concerning objects ‘spanned’ by a finite set of points. For example, we show that for any set . Similar problems involving point sets in higher dimensions are also studied.Most of our bounds are asymptotically tight, and they improve and generalize results of Chazelle, Edelsbrunner, Guibas, Hershberger, Seidel and Sharir [8], where weaker bounds for some of these cases were obtained.