### 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(nlogn)-time and O(n)-space algorithm is given.

Original language | English (US) |
---|---|

Article number | 101609 |

Journal | Computational Geometry: Theory and Applications |

Volume | 88 |

DOIs | |

State | Published - Jun 2020 |

### Keywords

- Inapproximability
- NP-hardness
- Optimal algorithm
- Skyline
- Stochastic points

## Fingerprint Dive into the research topics of 'The most-likely skyline problem for stochastic points'. Together they form a unique fingerprint.

## Cite this

Agrawal, A., Li, Y., Xue, J., & Janardan, R. (2020). The most-likely skyline problem for stochastic points.

*Computational Geometry: Theory and Applications*,*88*, [101609]. https://doi.org/10.1016/j.comgeo.2020.101609