Name
Abstract | ||
|---|---|---|
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. |
Year | Venue | Keywords |
|---|---|---|
2009 | Clinical Orthopaedics and Related Research | distance function,data structure,2 dimensional,computational geometry,voronoi diagram |
Field | DocType | Volume |
Skyline,Discrete mathematics,Binary logarithm,Power diagram,Combinatorics,Voronoi diagram,Weighted Voronoi diagram,Mathematics,Convex distance function | Journal | abs/0909.0 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Binay K. Bhattacharya | 1 | 332 | 49.20 |
| Arijit Bishnu | 2 | 134 | 22.25 |
| Otfried Cheong | 3 | 594 | 60.27 |
| Sandip Das | 4 | 256 | 48.78 |
| Arindam Karmakar | 5 | 20 | 5.92 |
| Jack Snoeyink | 6 | 2842 | 231.68 |