On Finding Non-dominated Points using Compact Voronoi Diagrams

Details On Finding Non-dominated Points using Compact Voronoi Diagrams On Finding Non-dominated Points using Compact Voronoi Diagrams

2009-09-04

arxiv.org/abs/0909.0814v1

Computer Science

Computational Geometry

11 pages, 3 figures

Scientific paper

We discuss in this paper a method of finding skyline or non-dominated points in 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 \not= 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 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((n_S + n_P)\log n_S + n_P \log n_P)$-time randomized incremental algorithm to find the non-dominated points.

Affiliated with

Also associated with

No associations

Rating

On Finding Non-dominated Points using Compact Voronoi Diagrams does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Finding Non-dominated Points using Compact Voronoi Diagrams, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Finding Non-dominated Points using Compact Voronoi Diagrams will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-35547