Deep Cliques in Point Sets

Abstract

Let n ∈ N and k ∈ N 0 . Given a set P of n points in the plane, apair {p, q} of points in P is called k-deep, if there are at least k pointsfrom P strictly on each side of the line spanned by p and q. A k-deepclique 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 onna line), there is a k-deep clique of size at least max{1, b k+1c}; this istight, for example in convex position. A k-deep clique in any set P ofnn points cannot have size exceeding n − d 3k2 e; this is tight for k ≤ 3 .nMoreover, for k ≤ b 2 c − 1, a k-deep clique cannot have size exceedingp2 n(b n 2 c − k); this is tight within a constant factor.We also pay special attention to ( n 2 − 1)-deep cliques (for n even),which are called halving cliques. These have been considered in theliterature by Khovanova and Yang, 2012, and they play a role in thelatter bound above. Every set P in general position with a halvingclique Q of size m must have at least b (m−1)(m+3)c points. If Q is in2convex position, the set P must have size at least m(m − 1). This istight, i.e., there are sets Q m of m points in convex position which canbe extended to a set of m(m − 1) points where Q m is a halving clique.Interestingly, this is not the case for all sets Q in convex position (evenif parallel connecting lines among point pairs in Q are excluded).