# Convex hull partition of a set of points

Given a set $$S$$ of $$n$$ points in $$\mathbb R^2$$, denote by $$\mathrm{convb}(S)$$ the boundary of the convex hull of $$S$$. Let \begin{align*} S_1 &= \mathrm{convb}(S)\\ S_{i+1} &= \mathrm{convb}\left(S \setminus \bigcup_{j=1}^i S_j\right). \end{align*}

Now $$S_1,\ldots$$ forms a partition of $$S$$. Is there an $$O(n\log n)$$ time algorithm for computing this partition?

• This partition is also known as the convex layers of a point set. The Wikipedia article also claims that there is indeed such an algorithm. – Discrete lizard May 17 at 12:48
• Ah, thanks a lot. The name convex layers makes a lot of sense. I didn't think of it hence could not find the relevant articles. – Mert Sağlam May 17 at 12:50
• It was published here: cs.princeton.edu/~chazelle/pubs/ConvexLayers.pdf – Mert Sağlam May 17 at 12:58