Expected Case for Projecting Points
Sergio Cabello, Matt DeVos, Bojan Mohar · 2006
Consider a set of n points in the plane with the property that any pair of points is at least at distance one. We study the expected concentration of the point set after projecting it onto a random graduated line. There is a lower bound of Ω ( √ n log n) given by Matoušek in [4], and we provide an upper bound of O(n 2/3). Povzetek: Analizirana je gostota točk v ravnini z razdaljo najmanj ena. 1