The Expected Number of Maximal Points of the Convolution of Two 2-D Distributions
Josep Dı́az, Mordecai J. Golin · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2019
The Maximal points in a set S are those that are not dominated by any other point in S. Such points arise in multiple application settings and are called by a variety of different names, e.g., maxima, Pareto optimums, skylines. Their ubiquity has inspired a large literature on the expected number of maxima in a set S of n points chosen IID from some distribution. Most such results assume that the underlying distribution is uniform over some spatial region and strongly use this uniformity in their analysis. This research was initially motivated by the question of how this expected number changes if the input distribution is perturbed by random noise. More specifically, let Bp denote the uniform distribution from the 2-dimensional unit ball in the metric Lp. Let δBq denote the 2-dimensional Lq-ball, of radius δ and Bp + δBq be the convolution of the two distributions, i.e., a point v ∈ Bp is reported with an error chosen from δBq. The question is how the expected number of maxima change as a function of δ. Although the original motivation is for small δ, the problem is well defined for any δ and our analysis treats the general case. More specifically, we study, as a function of n, δ, the expected number of maximal points when the n points in S are chosen IID from distributions of the type Bp + δBq where p, q ∈ {1, 2, ∞} for δ > 0 and also of the type B∞ + δBq where q ∈ [1, ∞) for δ > 0. For fixed p, q we show that this function changes “smoothly” as a function of δ but that this smooth behavior sometimes transitions unexpectedly between different growth behaviors. © Josep Diaz and Mordecai Golin.