Faster output-sensitive skyline computation algorithm

• We present a faster output-sensitive skyline computation algorithm which achieves 2nlog⁡k+2n2nlog⁡k+2n comparisons in worst case.
• Our algorithm does not rely on the existence of a linear time procedure for finding medians.
• Our algorithm uses a novel partitioning and eliminating strategy for skyline computation in two-dimensions.

We present the second output-sensitive skyline computation algorithm which is faster than the only existing output-sensitive skyline computation algorithm [1] in worst case because our algorithm does not rely on the existence of a linear time procedure for finding medians.