# On Finding Non-dominated Points using Compact Voronoi Diagrams - Computer Science > Computational Geometry

On Finding Non-dominated Points using Compact Voronoi Diagrams - Computer Science > Computational Geometry - Download this document for free, or read online. Document in PDF available to download.

Abstract: We discuss in this paper a method of finding skyline or non-dominated pointsin a set $P$ of $n P$ points with respect to a set $S$ of $n S$ sites. A point$p i \in P$ is non-dominated if and only if for each $p j \in P$, $j ot= i$,there exists at least one point $s \in S$ that is closer to $p i$ than $p j$.We reduce this problem of determining non-dominated points to the problem offinding sites that have non-empty cells in an additive Voronoi diagram with aconvex distance function. The weights of the additive Voronoi diagram arederived from the co-ordinates of the points of $P$ and the convex distancefunction is derived from $S$. In the 2-dimensional plane, this reduction givesa $On S + n P\log n S + n P \log n P$-time randomized incremental algorithmto find the non-dominated points.

Author: ** Binay Bhattacharya, Arijit Bishnu, Otfried Cheong, Sandip Das, Arindam Karmakar, Jack Snoeyink**

Source: https://arxiv.org/