Deep Cliques in Point Sets

Area of Science:

• Computational Geometry
• Combinatorial Geometry
• Discrete Mathematics

Background:

• Introduces the concept of k-deep pairs of points within a set P.
• Defines a k-deep clique as a subset of P where all pairs are k-deep.

Purpose of the Study:

• To establish tight bounds on the size of k-deep cliques in a set of n points.
• To investigate the properties and existence of halving cliques (a special case of k-deep cliques).

Main Methods:

• Analysis of geometric properties of point sets and their subsets.
• Derivation of lower and upper bounds for k-deep clique sizes.
• Examination of specific cases, including points in general position and convex position.

Main Results:

• A lower bound of \(\lceil n/2 \rceil\) for the size of a k-deep clique in a general position point set.
• An upper bound of \(\lfloor n^2/4 \rfloor\) for the size of a k-deep clique in any point set.
• Specific bounds for \(k = n/2\) (halving cliques), including necessary conditions on the total number of points for a given halving clique size.

Conclusions:

• The study provides tight bounds for k-deep clique sizes, demonstrating their existence and limitations.
• Results for halving cliques offer insights into their structure and relationship with the overall point set.
• The findings contribute to the understanding of geometric structures within point sets.