Computation of non-dominated points using compact Voronoi diagrams

Abstract

We discuss in this paper a method of finding skyline or non-dominated points in a set P of n points with respect to a set S of m sites. A point p(i) is an element of P is non-dominated if and only if for each p(j) is an element of P, j not equal i, there exists at least one point s is an element of S that is closer to p(i) than p(j). We reduce this problem of determining non-dominated points to the problem of finding sites that have non-empty cells in an additively weighted Voronoi diagram under convex distance function. The weights of the said 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((m + n) log m + n log n)-time randomized incremental algorithm to find the non-dominated points.