Opposite-Quadrant Depth in the Plane

摘要

Given a set S of n points in the plane, the opposite-quadrant depth of a point p∈S is defined as the largest number k such that there are two opposite axis-aligned closed quadrants (NW and SE, or SW and NE) with apex p, each quadrant containing at least k elements of S. We prove that S has a point with opposite-quadrant depth at least n/8. If the elements of S are in convex position, then we can guarantee the existence of an element whose opposite-quadrant depth is at least n/4. Both results are asymptotically best possible.