Opposite-quadrant depth in the plane

Abstract

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. © Springer-Verlag Tokyo 2007.