Deep Cliques in Point Sets

Let $$ and $$ . Given a set P of n points in the plane, a pair $$ of points in P is called k-deep, if there are at least k points from P strictly on each side of the line spanned by p and q. A k-deep clique is a subset of P with all its pairs k-deep. We show that if P is in general position (i.e., no three points on a line), there is a k-deep clique of size at least $$ ; this is tight, for example in convex position. A k-deep clique in any set P of n points cannot have size exceeding $$ ; this is tight for $$ . Moreover, for $$ , a k-deep clique cannot have size exceeding $$ ; this is tight within a constant factor. We also pay special attention to $$ -deep cliques (for n even), which are called halving cliques. These have been considered in the literature by Khovanova and Yang, 2012, and they play a role in the latter bound above. Every set P in general position with a halving clique Q of size m must have at least $$ points. If Q is in convex position, the set P must have size at least $$ . This is tight, i.e., there are sets $$ of m points in convex position which can be extended to a set of $$ points where $$ is a halving clique. Interestingly, this is not the case for all sets Q in convex position (even if parallel connecting lines among point pairs in Q are excluded).