Large area convex holes in random point sets Article uri icon

abstract

  • Let K,L be convex sets in the plane. For normalization purposes, suppose that the area of K is 1. Suppose that a set Kn of n points is chosen independently and uniformly over K, and call a subset of K a hole if it does not contain any point in Kn. It is shown that with high probability the largest area of a hole homothetic to L is (1 %2b o(1)) log n/n. We also consider the problems of estimating the largest area convex hole and the largest area of a convex polygonal hole; with vertices in Kn. For these two problems we give an answer that is asymptotically tight within a factor of 4. Copyright © by SIAM.

publication date

  • 2016-01-01