Article ID Journal Published Year Pages File Type
428895 Information Processing Letters 2015 4 Pages PDF
Abstract

•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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,