For a set O of n points in Rd, 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 oi∈O has an associated probability of existence pi∈(0,1]. The problem of computing the skyline with the maximum probability of occurrence is considered. It is shown that in Rd, d≥3, the problem is NP-hard and that the desired skyline cannot even be well-approximated in polynomial time unless P=NP. In R2, an optimal O(nlogn)-time and O(n)-space algorithm is given.
- Optimal algorithm
- Stochastic points