On Strong Centerpoints

2013/12/02 by Pradeesha Ashok, Ashok, Pradeesha, Sathish Govindarajan +1
Computer Science · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #cs.CG

paper · pdf · doi:10.48550/arxiv.1312.0387

arxiv created 2015/02/26 · arxiv updated 2015/02/27

Abstract

Let P be a set of n points in ℝ^d and F be a family of geometric objects. We call a point x ∈ P a strong centerpoint of P w.r.t F if x is contained in all F ∈ F that contains more than cn points from P, where c is a fixed constant. A strong centerpoint does not exist even when F 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

• Small Strong Epsilon Nets
• Extending the centerpoint theorem to multiple points
• On the concept of center for geometric objects and related problems
• Fitting centroids by a projective transformation
• Stationary radial centers and characterization of convex polyhedrons