TY - JOUR

T1 - The layer number of α-evenly distributed point sets

AU - Choi, Ilkyoo

AU - Joo, Weonyoung

AU - Kim, Minki

N1 - Funding Information:
Supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2018R1D1A1B07043049), and also by the Hankuk University of Foreign Studies, South Korea Research Fund.Partially supported by ISF, Israel Grant No. 2023464 and BSF, Israel Grant No. 2006099.
Publisher Copyright:
© 2020 Elsevier B.V.

PY - 2020/10

Y1 - 2020/10

N2 - For a finite point set in Rd, we consider a peeling process where the vertices of the convex hull are removed at each step. The layer number L(X) of a given point set X is defined as the number of steps of the peeling process in order to delete all points in X. It is known that if X is a set of random points in Rd, then the expectation of L(X) is Θ(|X|2∕(d+1)), and recently it was shown that if X is a point set of the square grid on the plane, then L(X)=Θ(|X|2∕3). In this paper, we investigate the layer number of α-evenly distributed point sets for α>1; these point sets share the regularity aspect of random point sets but in a more general setting. The set of lattice points is also an α-evenly distributed point set for some α>1. We find an upper bound of O(|X|3∕4) for the layer number of an α-evenly distributed point set X in a unit disk on the plane for some α>1, and provide an explicit construction that shows the growth rate of this upper bound cannot be improved. In addition, we give an upper bound of O(|X|[Formula presented]) for the layer number of an α-evenly distributed point set X in a unit ball in Rd for some α>1 and d≥3.

AB - For a finite point set in Rd, we consider a peeling process where the vertices of the convex hull are removed at each step. The layer number L(X) of a given point set X is defined as the number of steps of the peeling process in order to delete all points in X. It is known that if X is a set of random points in Rd, then the expectation of L(X) is Θ(|X|2∕(d+1)), and recently it was shown that if X is a point set of the square grid on the plane, then L(X)=Θ(|X|2∕3). In this paper, we investigate the layer number of α-evenly distributed point sets for α>1; these point sets share the regularity aspect of random point sets but in a more general setting. The set of lattice points is also an α-evenly distributed point set for some α>1. We find an upper bound of O(|X|3∕4) for the layer number of an α-evenly distributed point set X in a unit disk on the plane for some α>1, and provide an explicit construction that shows the growth rate of this upper bound cannot be improved. In addition, we give an upper bound of O(|X|[Formula presented]) for the layer number of an α-evenly distributed point set X in a unit ball in Rd for some α>1 and d≥3.

KW - Convex layer

KW - Evenly-distributed point set

KW - Peeling sequence

UR - http://www.scopus.com/inward/record.url?scp=85086570371&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2020.112029

DO - 10.1016/j.disc.2020.112029

M3 - Article

AN - SCOPUS:85086570371

VL - 343

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 10

M1 - 112029

ER -