Name
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 pi∈P is non-dominated if and only if for each pj∈P, $j \not= 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 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)logm+n logn)-time randomized incremental algorithm to find the non-dominated points. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-11440-3_8 | WALCOM |
Keywords | Field | DocType |
non-dominated point,incremental algorithm,compact voronoi diagram,n point,convex distance function,n logn,set p,2-dimensional plane,additively weighted voronoi diagram,voronoi diagram,point pi,distance function,2 dimensional | Skyline,Discrete mathematics,Power diagram,Combinatorics,Centroidal Voronoi tessellation,Bowyer–Watson algorithm,Lloyd's algorithm,Voronoi diagram,Weighted Voronoi diagram,Mathematics,Computation | Conference |
Volume | ISSN | ISBN |
5942 | 0302-9743 | 3-642-11439-3 |
Citations | PageRank | References |
2 | 0.36 | 10 |
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 |