Peeling the grid

DOI10.1137/120892660MaRDI QIDQ2848527zbMATH OpenOpenAlexFDO

Authors Bernard Lidický, Sariel Har-Peled

Publication date 26 September 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.3200

zbMATH Keywords

convex hullgridpeeling

Mathematics Subject Classification ID

Lattices and convex bodies in (2) dimensions (aspects of discrete geometry) (52C05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Consider the set of points formed by the integer $nimesn$ 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(n^{4/3}); that is, the number of convex layers of the $nimesn$ grid is Theta(n^{4/3}).

Recommendations

• New estimates for convex layer numbers
• The layer number of \(\alpha \)-evenly distributed point sets
• Counting the onion

Cited in

(8)

• On separating points by lines
• New estimates for convex layer numbers
• Peeling or not peeling—is that the question?
• Geometric covering number: covering points with curves
• Grid peeling of parabolas
• Peeling sequences
• The minimum number of peeling sequences of a point set
• The layer number of \(\alpha \)-evenly distributed point sets

This page was built for publication: Peeling the grid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848527)