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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Discrete lizard May 17 at 12:48
  • $\begingroup$ 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. $\endgroup$ – Mert Sağlam May 17 at 12:50
  • 1
    $\begingroup$ It was published here: cs.princeton.edu/~chazelle/pubs/ConvexLayers.pdf $\endgroup$ – Mert Sağlam May 17 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.