Skip to main content
profile image
Selected Works of Bernard Lidický
Article
Peeling the Grid
SIAM Journal on Discrete Mathematics (2013)
  • Sariel Har-Peled, University of Illinois at Urbana-Champaign
  • Bernard Lidicky, University of Illinois at Urbana-Champaign
Download Find in your library
Abstract
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 On4/3; that is, the number of convex layers of the n × n
grid is Θn4/3.
Keywords
  • grid,
  • peeling,
  • convex hull
Disciplines
Publication Date
2013
DOI
10.1137/120892660
Publisher Statement
Copyright 2013 Society for Industrial and Applied Mathematics
Citation Information
Sariel Har-Peled and Bernard Lidicky. "Peeling the Grid" SIAM Journal on Discrete Mathematics Vol. 27 Iss. 2 (2013) p. 650 - 655
Available at: http://works.bepress.com/bernard-lidicky/7/
Creative Commons license
Creative Commons License
This work is licensed under a Creative Commons CC_BY-NC International License.