  Skyline queries are important in many application domains. In this paper, we
propose a novel structure Skyline Diagram, which given a set of points,
partitions the plane into a set of regions, referred to as skyline polyominos.
All query points in the same skyline polyomino have the same skyline query
results. Similar to $k^{th}$-order Voronoi diagram commonly used to facilitate
$k$ nearest neighbor ($k$NN) queries, skyline diagram can be used to facilitate
skyline queries and many other applications. However, it may be computationally
expensive to build the skyline diagram. By exploiting some interesting
properties of skyline, we present several efficient algorithms for building the
diagram with respect to three kinds of skyline queries, quadrant, global, and
dynamic skylines. In addition, we propose an approximate skyline diagram which
can significantly reduce the space cost. Experimental results on both real and
synthetic datasets show that our algorithms are efficient and scalable.
