کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428895 | 686958 | 2015 | 4 صفحه PDF | دانلود رایگان |
• We prove a strong centerpoint for a class of convex polytopes with fixed orientations.
• We prove a strong centerpoint for set systems with bounded intersection.
• We prove a strong centerpoint for geometric set systems defined by lines and circles.
Let P be a set of n points in RdRd and FF be a family of geometric objects. We call a point x∈Px∈P a strong centerpoint of P w.r.t. FF if x is contained in all F∈FF∈F that contains more than cn points of P, where c is a fixed constant. A strong centerpoint does not exist even when FF is the family of halfspaces in the plane. We prove the existence of strong centerpoints with exact constants for convex polytopes defined by a fixed set of orientations. We also prove the existence of strong centerpoints for abstract set systems with bounded intersection.
Journal: Information Processing Letters - Volume 115, Issue 3, March 2015, Pages 431–434