Selecting out a maxima set of points from among a set of points in the plane seems is intended to filter away a lot of points from consideration in a multiobjective optimization problem. For example, if we grade hotels by the sizes of their pools and the quality of their restaurants, then we would hope to have a small set of hotels to choose from that are not dominated by any other hotel along these axes. So let us analyze the expected size of a maxima set of randomly chosen points in the plane with distinct x- and y-coordinates. We can model such as set by defining a random set of n points in the plane by first randomly permuting the sequence of numbers, (1, 2,...,n), giving (y₁, y₂,...,y_n). Let us then define a set of two dimensional points as the set, 

Since it is the relative order of points that determines whether a point is a maximum point or not, this set of points with integer coordinates fully captures all the possibilities, with respect to the maxima-set problem, for any random set of points in the plane with distinct x- and y-coordinates. So as to show just how effective it is to select out the maxima set of points from such a set as a filtering step (hence, it should be a good filter in practice), show that the expected size of the maxima set for R is O(log n).

Transcribed Image Text:

R = {(1, y1), (2, Y2), ..., (n, yn)}