On Finding Non-dominated Points using Compact Voronoi Diagrams
Binay Kumar Bhattacharya, Arijit Bishnu, Otfried Cheong, Sandip Das, Arindam Karmakar, Jack Scott Snoeyink · arXiv (Cornell University) · 2009
We discuss in this paper a method of finding skyline or non-dominated points in a set P of nP points with respect to a set S of nS sites. A point pi ∈ P is non-dominated if and only if for each pj ∈ P, j ̸ = i, there exists at least one point s ∈ S that is closer to pi than pj. We reduce this problem of determining non-dominated points to the problem of finding sites that have non-empty cells in an additive Voronoi diagram with a convex distance function. The weights of the additive Voronoi diagram are derived from the co-ordinates of the points of P and the convex distance function is derived from S. In the 2-dimensional plane, this reduction gives a O((nS + nP) log nS + nP log nP)-time randomized incremental algorithm to find the non-dominated points. 1