Computation of spatial skyline points

DOI10.1016/J.COMGEO.2020.101698MaRDI QIDQ827323zbMATH OpenOpenAlexFDO

Authors Arijit Bishnu, Sandip Das, Arindam Karmakar, Binay Bhattacharya, Otfried Cheong, Jack Snoeyink

Publication date 7 January 2021

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0909.0814

zbMATH Keywords

Voronoi diagramspatial databasesdominated pointsline-sweep algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Database theory (68P15)

Abstract: We discuss a method of finding skyline or non-dominated sites in a set $P$ of $n$ point sites with respect to a set $S$ of $m$ points. A site $pinP$ is non-dominated if and only if for each $qinPsetminusp$, there exists at least one point $sinS$ that is closer to $p$ than to $q$. We reduce this problem of determining non-dominated sites to the problem of finding sites that have non-empty cells in an additively weighted Voronoi diagram under a convex distance function. The weights of said Voronoi diagram are derived from the coordinates of the sites of $P$, while the convex distance function is derived from $S$. In the two-dimensional plane, this reduction gives an $O((n+m)log(n+m))$-time algorithm to find the non-dominated points.

Recommendations

• Computation of non-dominated points using compact Voronoi diagrams
• Top-\(k\) Manhattan spatial skyline queries
• Top-\(k\) Manhattan spatial skyline queries
• MSSQ: Manhattan spatial skyline queries
• Optimal planar orthogonal skyline counting queries

Cites work

• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 741008 (Why is no real title available?)
• scientific article; zbMATH DE number 1391661 (Why is no real title available?)
• A compact piecewise-linear Voronoi diagram for convex sites in the plane
• Computation of non-dominated points using compact Voronoi diagrams
• Convex Bodies The Brunn-MinkowskiTheory
• On Finding the Maxima of a Set of Vectors
• Top-\(k\) Manhattan spatial skyline queries

Cited in

(8)

• Faster output-sensitive skyline computation algorithm
• Computation of non-dominated points using compact Voronoi diagrams
• MSSQ: Manhattan spatial skyline queries
• Faster distance-based representative skyline and \(k\)-center along Pareto front in the plane
• Efficient processing of the skyline-CL query
• Top-\(k\) Manhattan spatial skyline queries
• The most-likely skyline problem for stochastic points
• Top-\(k\) Manhattan spatial skyline queries

Describes a project that uses

Uses Software

• Voronoi

This page was built for publication: Computation of spatial skyline points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q827323)