In-Place Algorithms for Computing (Layers of) Maxima
Henrik Blunck, Jan Vahrenhold · Algorithmica · 2008
We describe space-efficient algorithms for solving problems related to finding maxima among points in two and three dimensions. Our algorithms run in optimal $\mathcal{O}(n\log n)$ time and occupy only constant extra space in addition to the space needed for representing the input.