Computation of spatial skyline points

Abstract

The database skyline query (or non-domination query) has a spatial form: Given a setPwithnpoint sites, and a point set S of m locations of interest, a site p is an element of P is a skyline point if and only if for each q is an element of P\{p}, there exists at least one location s is an element of S that is closer topthan toq. We reduce the problem of determining skyline points to the problem of finding sites that have non-empty cells in an additively weighted Voronoi diagram under a convex distance function. The weights of said Voronoi diagram are derived from the coordinates of the sites ofP, while the convex distance function is derived from the set of locationsS. In the two-dimensional plane, this reduction gives an O((n + m) log(n + m))-time algorithm to find the skyline points.