Let $C_n$ denote the convex hull of all integer vectors $(x,y)\in\mathbb{R}^2$ satisfying $x^2+y^2\leq n$. What can be said about the number of vertices of $C_n$ and the number of integer points on the boundary of $C_n$? Are there nice asymptotic formulas, possibly for special values of $n$?
$\begingroup$
$\endgroup$
4
asked Jan 10, 2012 at 21:16
-
1$\begingroup$ Pick's theorem states that $A=i+b/2-1$, where $A$ is the area of the region, $i$ is the number of interior points, and $b$ is the number of points on the boundary. $\endgroup$– Kevin O'BryantJan 10, 2012 at 21:25
-
2$\begingroup$ I am guessing Richard knows that, the area is the tricky part... $\endgroup$– Igor RivinJan 10, 2012 at 21:34
-
1$\begingroup$ Interesting question. It should be feasible to generate a lot of numerical data, which might be suggestive of the actual asymptotics. $\endgroup$– Noam D. ElkiesJan 10, 2012 at 21:43
-
$\begingroup$ Your question is roughly equivalent to the question asking for the Ehrhart polynomials of the polytops $C_n$. Area gives the leading coefficient and numbers of vertices and boundary points the linear term (the constant term is always $1$). $\endgroup$– Roland BacherJan 11, 2012 at 9:05
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
3
Asymptotic formulas might be asking for a lot, but there is some work by I. Barany et al. See:
RANDOM POINTS AND LATTICE POINTS IN CONVEX BODIES IMRE BA ́RA ́NY (in BAMS 2008) and the paper referred to therein by Balog/Barany:
Balog, Antal(H-AOS); Bárány, Imre(H-AOS) On the convex hull of the integer points in a disc. Discrete and computational geometry (New Brunswick, NJ, 1989/1990), 39–44, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 6, Amer. Math. Soc., Providence, RI, 1991. 11H06 (11P21 52C07)
The former talks about some nice probabilistic results, the latter shows that there is an estimate of the form $c_1r^{2/3} \leq N(r) \leq c_2 r^{2/3},$ where $N(r) = C_n,$ and $r=n$ in your notation.
EDIT Answering my own question in the comments: it is a result of Renyi-Sulanke, 1963, that for $n$ random points in the disk, the expected number of extremal points is $O(n^{1/3}),$ so this is of the same order as for lattice points. A bit surprising.
answered Jan 10, 2012 at 21:43
-
$\begingroup$ The exponent $2/3$ suggests a relation with Jarnik's theorem on the minimum area of a convex lattice $N$-gon. $\endgroup$ Jan 11, 2012 at 4:23
-
1$\begingroup$ Actually, I wonder what the exponent is for RANDOM points in the disk. $\endgroup$ Jan 12, 2012 at 22:03
-
1
$\begingroup$
$\endgroup$
2
Not really an answer, but perhaps it will spare somebody else an attempt at "proof by encyclopedia".
Pick's theorem states that $A=i+b/2-1$, where $A$ is the area of the region, i is the number of interior points, and $b$ is the number of points on the boundary.
A057665 gives the number of integer pairs $(x,y)$ with $x^2+y^2\leq n$.
If my calculations are correct, the number of points on the boundary are 4, 8, 8, 8, 12, 12, 12, 16, 8, 16, ..., which is not in the OEIS.
The area of the convex hull is 2, 4, 4, 8, 14, 14, 14, 16, 24, 28, ..., which is also not in the OEIS.
answered Jan 10, 2012 at 21:44
-
$\begingroup$ I see the $4,8,8$ corresponding to $n=1,2,4$ but then for $n=5$ the boundary has $12$ points (albeit $8$ vertices.) $\endgroup$ Jan 10, 2012 at 22:11
-
$\begingroup$ @Aaron: We agree, I think. I include $n=3$ in the list. $\endgroup$ Jan 11, 2012 at 3:30
$\begingroup$
$\endgroup$
answered Jan 7, 2014 at 9:39