2025/12/20 by Apfelbaum, Roel, Ben-Dan, Itay, Felsner, Stefan +4
paper · doi:10.20382/v2i1a7
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 an extremal version of this problem. A pair (a,b) of numbers is admissible if every point set P contains a point p in 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. In higher dimensions, we study the maximum a such that (a,a) is opposite-orthant admissible. In dimension d, we show that 1/(2γ)≤a≤1/γ for γ=22d-12d-1. Finally we deal with a variant of the problem where the opposite pairs of orthants need not be determined by a point in P. Again we are interested in values a, such that all subsets P in Rd admit a pair (O,Oop) of opposite orthants both ontaining at least an a-fraction of the points. The maximum such value is a=1/2d. Generalizations of the problem are also disussed.