Peeling the grid

Sariel Har-Peled, Bernard Lidický

Research output: Contribution to journalArticlepeer-review


Consider the set of points formed by the integer n × n grid and the process that in each iteration removes from the point set the vertices of its convex hull. Here, we prove that the number of iterations of this process is O(n4/3); that is, the number of convex layers of the n × n grid is θ(n4/3).

Original languageEnglish (US)
Pages (from-to)650-655
Number of pages6
JournalSIAM Journal on Discrete Mathematics
Issue number2
StatePublished - 2013


  • Convex hull
  • Grid
  • Peeling

ASJC Scopus subject areas

  • Mathematics(all)


Dive into the research topics of 'Peeling the grid'. Together they form a unique fingerprint.

Cite this