On strong centerpoints

DOI10.1016/J.IPL.2014.11.004zbMATH Open1318.52016arXiv1312.0387OpenAlexW2963360854MaRDI QIDQ483053FDOQ483053

Authors: Pradeesha Ashok, Sathish Govindarajan 

Publication date: 15 December 2014

Published in: Information Processing Letters (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1312.0387

Recommendations

• The strong centre conjecture: an invariant theory approach
• On strong \(P\)-points
• scientific article; zbMATH DE number 1361453
• A new and stronger central sets theorem
• An optimal extension of the centerpoint theorem
• On the strong fixed point property
• scientific article; zbMATH DE number 17652
• On center manifolds
• scientific article; zbMATH DE number 2167034

zbMATH Keywords

discrete geometryconvex polytopeshyperplanescenterpointstrong centerpoint

Mathematics Subject Classification ID

(n)-dimensional polytopes (52B11) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07)

Cites Work

• The number of triangles covering the center of an \(n\)-set
• \(\epsilon\)-nets and simplex range queries
• Small strong epsilon nets
• Computing a centerpoint of a finite planar set of points in linear time
• Approximate center points in dense point sets
• Title not available (Why is that?)
• Separators for sphere-packings and nearest neighbor graphs
• A Theorem on General Measure
• Small weak epsilon-nets
• An optimal extension of the centerpoint theorem
• Approximate centerpoints with proofs
• Title not available (Why is that?)
• Partitioning with two lines in the plane

Cited In (3)

• An optimal generalization of the centerpoint theorem, and its extensions
• \(k\)-centerpoints conjectures for pointsets in \(\mathbb{R}^d\)
• Extending the centerpoint theorem to multiple points

This page was built for publication: On strong centerpoints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q483053)