Selecting points that are heavily covered by pseudo-circles, spheres or rectangles Academic Article uri icon


  • Abstract 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 $ P $ of $ n $ points in $\R^ 2$ and any set $ C $ of $ m\,{\geq}\, 4n $ distinct pseudo-circles, each passing through a distinct pair of points of $ P $, there is a point in $ P $ that is covered by (ie, lies in the interior of) $\Omega (m^ 2/n^ 2) $ pseudo-circles of $ C $. Similar problems involving point sets in higher dimensions are also studied.

publication date

  • January 1, 2004