The convex hull of the lattice points inside a curve
- PDF / 268,535 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 41 Downloads / 188 Views
The convex hull of the lattice points inside a curve M. N. Huxley
© Akadémiai Kiadó, Budapest, Hungary 2014
Abstract Let C be a smooth convex closed plane curve. The C-ovals C(R, u, v) are formed by expanding by a factor R, then translating by (u, v). The number of vertices V (R, u, v) of the convex hull of the integer points within or on C(R, u, v) has order R 2/3 (Balog and Bárány) and has average size B R 2/3 as R varies (Balog and Deshouillers). We find the space average of V (R, u, v) over vectors (u, v) to be B R 2/3 with an explicit coefficient B, and show that the average over R has the same B. The proof involves counting edges and finding the domain D(q, a) of an integer vector, the set of (u, v) for which the convex hull has a directed edge parallel to (q, a). The resulting sum over bases of the integer lattice is approximated by a triple integral. Keywords Convex hull · Lattice points · Integer points · Number of vertices · Kloosterman sums · Plane domains Mathematics Subject Classification
11H06 · 52C05 · 11P21
1 Introduction Let C be a smooth convex closed curve in the plane, with a designated interior point A, the centre. The family of C-ovals are the curves C(R, u, v) formed by enlarging C by a factor R, with the centre A fixed, and then translating the centre from A to the point (u, v). The oval C(R, u, v) bounds a closed convex set S(R, u, v). In a series of papers [3–6,10] we have studied the set J (R, u, v) of integer points in the set S(R, u, v) for R large. In this paper we consider the polygon K (R, u, v) which is the convex hull of the set J (R, u, v) of integer points. Bárány asks (originally for the case when C is the unit circle) whether there is a constant B such that the the polygon K (R, u, v) has approximately B R 2/3 vertices. Let V (R, u, v) be the actual number of vertices of the polygon K (R, u, v). Balog and Bárány [1]
M. N. Huxley (B) School of Mathematics, University of Cardiff, 23 Senghenydd Road, Cardiff CF24 4YH, Wales, UK e-mail: [email protected]
123
M. N. Huxley
showed that for the unit circle 1 2/3 ≤ V (R, 0, 0) ≤ 6R 2/3 . R 4 Balog and Deshouillers [2] found that V (R, 0, 0) has an average asymptotically B R 2/3 over short intervals of R, again for the unit circle, but the method, they say, works for general ovals. The value of B, approximately 3.4, is given by a multiple integral. In this paper we show in Theorem 1.1 that V (R, u, v) has average asymptotically B R 2/3 taken over translation vectors (u, v). The coefficient B is the volume of a three-dimensional region, and it involves integrals of the cube roots of rational functions. We obtain a weaker version of the Balog-Deshouillers theorem for the circle as Theorem 1.2. This shows that we have the same value of B as Balog and Deshouillers in this case; they do not state the value of B in general. Our method gives the same coefficient B, independent of the shape and orientation of the oval C, under a natural normalisation of the size. For the unit circle, there are 80 different polygons K (2.501, u, v) up
Data Loading...
