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(n log n)-time and O(n)-space algorithm is given.
|Original language||English (US)|
|Number of pages||6|
|State||Published - 2017|
|Event||29th Canadian Conference on Computational Geometry, CCCG 2017 - Ottawa, Canada|
Duration: Jul 26 2017 → Jul 28 2017
|Conference||29th Canadian Conference on Computational Geometry, CCCG 2017|
|Period||7/26/17 → 7/28/17|
Bibliographical noteFunding Information:
The research of the first author was supported, in part, by a Doctoral Dissertation Fellowship from the Graduate School of the University of Minnesota.
Compilation copyright © 2017 Michiel Smid Copyright of individual papers retained by authors.All right reserved.