Abstract
Let n ∈ N and k ∈ N0 . Given a set P of n points in the plane, a pair {p, q} 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 max {1, ⌊1/⌋} ; this is tight, for example in convex position. A k-deep clique in any set P of n points cannot have size exceeding n - ⌈3/2⌉ ; this is tight for k ≤ 3/ . Moreover, for k ≤ ⌊2/⌋ - 1 , a k-deep clique cannot have size exceeding [Formula: see text] ; this is tight within a constant factor. We also pay special attention to (2/ - 1) -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 m(m - 1) . This is tight, i.e., there are sets Qm of m points in convex position which can be extended to a set of m(m - 1) points where Qm 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).