Two Lower Bounds for Random Point Sets via Negative Association

Description

We present two lower bounds that hold with high probability for random point sets. We first give a new, and elementary, proof that the classical models of random point sets (uniform in a smooth convex body, uniform in a polygon, Gaussian) have a superconstant number of extreme points with high probability. We next prove that any algorithm that determines the orientation of all triples in a planar set of n points (that is, the order type of the point set) from their Cartesian coordinates must read with high probability $4n \log n − O(n \log \log n)$ coordinate bits. This matches previously known upper bounds. Both bounds rely on a method due to Dubhashi and Ranjan (Random Structures and Algorithms, 1998) for obtaining concentration results via a negative association property.

Additional details