2D Minimal

Finding minimals of points (instead of minimums), i.e. no point has both $x$ and $y$ greater than me.

Solution

• Utilizes prune-and-search idea.
• Find the median of $x$-coordinates (according to selection-problem).
• Divide the points into left and right sets, denoted as $L$ and $R$.
• In $R$, find the points with the biggest $y$-coordinate as $p^{\ast }$
• In $L$, eliminate all points with $y$-coordinate less than or equal to that of $p^{\ast }$, gives $L^{\prime }$. Similarly get $R^{\prime }$.
• Recurse on $L^{\prime }$ and $R^{\prime }$.

Analysis

$$T(n,h)=T\left(\frac{n}{2},h^{\prime }\right)+T\left(\frac{n}{2},h-h^{\prime }\right)+an$$