The most-likely skyline problem for stochastic points

Abstract 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 2 , an optimal O ( n log ⁡ n ) -time and O ( n ) -space algorithm is given.