کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414846 | 681058 | 2010 | 8 صفحه PDF | دانلود رایگان |
Using a technique that Tverberg and Vrecica (1993) [16] discovered to give a surprisingly simple proof of Tverberg's theorem, we show the following extension of the centerpoint theorem. Given any set P of n points in the plane, and a parameter 1/3⩽c⩽1, one can always find a disk D such that any closed half-space containing D contains at least cn points of P. Furthermore, D contains at most (3c−1)n/2 points of P (the case c=1 is trivial – take any D containing P; the case c=1/3 is the centerpoint theorem). We also show that, for all c, this bound is tight up to a constant factor. We extend the upper bound to Rd. Specifically, we show that given any set P of n points, one can find a ball D containing at most ((d+1)c−1)n/d points of P such that any half-space containing D contains at least cn points of P.
Journal: Computational Geometry - Volume 43, Issues 6–7, August 2010, Pages 593-600