On strong centerpoints

DOI10.1016/J.IPL.2014.11.004MaRDI QIDQ483053zbMATH OpenOpenAlexFDO

Authors Pradeesha Ashok, Sathish Govindarajan

Publication date 15 December 2014

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

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

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)

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.

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

Cites work

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

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)