Maxima in convex regions

摘要: Suppose that C is a bounded convex region. Let pl, . , p,, be points drawn from the uniform distribution over and let M,” number of which are maximal. In this note we examine asymptotics E (M$‘) as n -t 00. We show, for example, if planar then, either (M$) = 0 (6) or (Mz) (log n) give simple geometric criterion tells two behaviors applies. This also addresses when higher-dimension,al region, discusses asymptotic behavior higher moments well. Some immediate algorithmic implications follow knowing examined, e.g., existence heuristics finding maxima have fast expected running times their input any many different possible distributions.