Points with large quadrant-depth
Roel Apfelbaum, Itay Ben-Dan, Stefan Felsner, Rom Pinchasi, Tillmann Miltzow · 2010
Given a set P of points in the plane we are interested in points that are 'deep' in the set in the sense that they have two opposite quadrants both containing many points of P. We deal with the extremal version of this problem. A pair (a, b) of numbers is admissible if every point set P contains a point p ∈ P that determines a pair (Q,Qop) of opposite quadrants, such that Q contains at least an a-fraction and Qop contains at least a b-fraction of the points of P. We provide a complete description of the set F of all admissible pairs (a, b). This amounts to identifying three line segments and a point on the boundary of F.