# 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^*$ - In $L$, eliminate all points with $y$-coordinate less than or equal to that of $p^*$, gives $L'$. Similarly get $R'$. - Recurse on $L'$ and $R'$. ## Analysis $ T(n, h) = T\left(\frac n2, h'\right) + T\left(\frac n2, h-h'\right) + an $