Mordecai Golin, {\sc Inria}-Rocquencourt

How many Maxima can there be?

Let $C$ be a planar region and let $S = \{p_1,\ldots,p_n\}$ be a set of $n$ points chosen Independently Identically Distributed from the uniform distribution over $C.$ Set $M_n^C$ to be the number of the points in $S$ that are maximal. We will discuss how the geometry of $C$ influences the asymptotic behaviour of $E\left(M_n^C\right)$ as $n \rightarrow \infty.$ In particular we will show that if $C$ is convex then the asymptotic order behaviour of $E\left(M_n^C\right)$ can be inferred from only a small amount of geometric information about $C.$ We will also discuss some immediate algorithmic implications of these results.