Given a set of points (on the left). The silhouette set of these points is shown to the right.
In this problem, all rectangles are defined by two points, $(0, 0)$ and $(x_i, x_j)$. Formally, for a set of points $P$, a point, $(x_1,y_1) \in P$ is in the silhouette set of $P$ if for any other point $(x_j, y_j) \in P$, $x_j\ge x_i$ and $y_j\ge y_i$.
How can we prove that any algorithm that computes the 'silhouette set' is $\Omega(n \lg n)$ under a comparison-based sorting algorithm?
We can assume no duplicate points in given set of points
Input: An array of pairs of integers (x, y)
Output: An array pairs of integers such that its elements give the coordinates of all the silhouette points, listed from left to right.
Note that we are asked to prove that the lower bound of any comparison-based sorting approach to this problem is $Ω(n \lg n)$, not design the algorithm itself
Some of my Ideas
We know that the worst-case running time of any algorithm for sorting an array of integers is
Ω(n lg n).We could sort each of the sets $[x_1, x_2, x_3, \cdots]$ and $[y_1, y_2, y_3, \cdots]$
I am fairly stuck with any other ideas; this question trumps me greatly and I'd absolutely appreciate any help with this.
Given a sequence of distinct numbers $A = \langle a_1, \cdots, a_n \rangle$, we can use the silhoutte algorithm to sort $A$. Associate $a_i$ with the point $(a_i, -a_i)$. Clearly for any two different points $a_j$ and $a_k$, either $a_i > a_j$ or $-a_i > -a_j$, thus all points must be in the silhouette set. Additionally, the silhouette algorithm will give these points in a sorted order from left to right and thus this corresponds exactly to $A$ in a sorted order.