Points with large quadrant depth

Roel Apfelbaum, Itay Ben-Dan, Stefan Felsner, Tillmann Miltzow, Rom Pinchasi, Torsten Ueckerdt, Ran Ziv


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 thatQ 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 inRd 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.

Full Text:


DOI: http://dx.doi.org/10.20382/jocg.v2i1a7

ISSN: 1920-180X