33-2 Maximal layers

Let $Q$ be a set of $n$ points in the plane. We say that point $(x, y)$ dominates point $(x', y')$ if $x \ge x'$ and $y \ge y'$. A point in $Q$ that is dominated by no other points in $Q$ is said to be maximal. Note that $Q$ may contain many maximal points, which can be organized into maximal layers as follows. The first maximal layer $L_1$ is the set of maximal points of $Q$. For $i > 1$, the $i$th maximal layer $L_i$ is the set of maximal points in $Q - \bigcup_{j = 1}^{i - 1} L_j$.

Suppose that $Q$ has $k$ nonempty maximal layers, and let $y_i$ be the $y$-coordinate of the leftmost point in $L_i$ for $i = 1, 2, \dots, k$. For now, assume that no two points in $Q$ have the same $x$- or $y$-coordinate.

a. Show that $y_1 > y_2 > \cdots > y_k$.

Consider a point $(x, y)$ that is to the left of any point in $Q$ and for which $y$ is distinct from the $y$-coordinate of any point in $Q$. Let $Q' = Q \cup \{(w, y)\}$.

b. Let $j$ be the minimum index such that $y_j < y$, unless $y < y_k$, in which case we let $j = k + 1$. Show that the maximal layers of $Q'$ are as follows:

• If $j \le k$, then the maximal layers of $Q'$ are the same as the maximal layers of $Q$, except that $L_j$ also includes $(x, y)$ as its new leftmost point.

• If $j = k + 1$, then the first $k$ maximal layers of $Q'$ are the same as for $Q$, but in addition, $Q'$ has a nonempty $(k + 1)$st maximal layer: $L_{k + 1} = \{(x, y)\}$.

c. Describe an $O(n\lg n)$-time algorithm to compute the maximal layers of a set $Q$ of $n$ points. ($\textit{Hint:}$ Move a sweep line from right to left.)

d. Do any difficulties arise if we now allow input points to have the same $x$- or $y$-coordinate? Suggest a way to resolve such problems.

(Omit!)