The most-likely skyline problem for stochastic points

For a set O of n points in R^d, the skyline consists of the subset of all points of O where no point is dominated by any other point of O. Suppose that each point o_i∈O has an associated probability of existence p_i∈(0,1]. The problem of computing the skyline with the maximum probability of occurrence is considered. It is shown that in R^d, d≥3, the problem is NP-hard and that the desired skyline cannot even be well-approximated in polynomial time unless P=NP. In R², an optimal O(nlog⁡n)-time and O(n)-space algorithm is given.