The number of lattice points on a convex curve

If C is a strictly convex plane curve of length l, it has been known for a long time that the number of integer lattice points on C is $\text{O(l}{}^{\mathrm{<mtext>2</mtext><mtext>3</mtext>}}\text{)}$ and the exponent is best possible. In this paper, it is shown that the exponent can be decreased by imposing suitable smoothness conditions on C; in particular, if C has a continuous third derivative with a sensible bound, the best possible value of the exponent lies between $\text{3}\text{5}$ and $\text{1}\text{3}$ inclusive.     

On triangulations of the convex hull ofn points

A setS ofn points in Euclideand-space determines a convex hull which can be triangulated into some numberm of simplices using the points ofS as vertices. We characterize those setsS for which all triangulations minimizem. This is used to characterize sets of points maximizing the volume of the smallest non-trivial simplex. This work was supported in part by NSF Grants MCS 81-02519 and MCS 82-03347. This work supported in part by NSF Grants MCS 81-02519 and MCS 82-03347 Dedicated to Paul Erdős on his seventieth birthday     

Quadratic problems defined on a convex hull of points

In this paper we consider an algorithm for a class of quadratic problems defined on a polytope which is described as the convex hull of a set of points. The algorithm is based on simplex partitions using convex underestimating functions.     

The order of points on the second convex hull of a simple polygon

Given a setV of points on the plane, if {q ₁,...,q _n } is the set of points on the second convex hull ofV, the order in which these points are visited in anyV-gon is characterized. This order must verify two similar conditions to those of Kuratowski's theorem for planar graphs. Moreover, the number of possible orders that verify these conditions is obtained. It isO(5 ⁿ ).     

On the convex hull of uniform random points in a simpled-polytope

Denote the expected number of facets and vertices and the expected volume of the convex hullP _n ofn random points, selected independently and uniformly from the interior of a simpled-polytope byE _n (f), E _n (v), andE _n (V), respectively. In this note we determine the sharp constants of the asymptotic expansion ofE _n (f), E _n (v), andE _n (V), asn tends to infinity. Further, some results concerning the expected shape ofP _n are given. The work of F. Affentranger was supported by the Swiss National Foundation.     

Distribution-independent properties of the convex hull of random points

Denote byV _n ^(d) the expected volume of the convex hull ofn points chosen independently according to a given probability measure in Euclideand-spaceE ^d. Ifd=2 ord=3 and is the measure corresponding to the uniform distribution on a convex body inE ^d, Affentranger and Badertscher derived that

On the interior lattice points of convex lattice 11-gon

A lattice point in the plane is a point with integer coordinates. A lattice polygon K is a polygon whose vertices are lattice points. In this note we prove that any convex lattice 11-gon contains at least 15 interior lattice points.     

On the shape of the convex hull of random points

Summary Denote by E _n the convex hull of n points chosen uniformly and independently from the d-dimensional ball. Let Prob(d, n) denote the probability that E _n has exactly n vertices. It is proved here that Prob(d, 2 ^d/2 d ^-)1 and Prob(d, 2 ^d/2 d ^(3/4)+)0 for every fixed >0 when d. The question whether E _n is a k-neighbourly polytope is also investigated.     

On the complexity of finding the convex hull of a set of points

An n log n lower bound is found for linear decision tree algorithms with integer inputs that either identify the convex hull of a set of points or compute its cardinality.     

Extreme points of the closed convex hull of composition operators

We study the extreme points of the closed convex hull of the set of all composition operators on the space of bounded analytic functions and the disk algebra.     

Primitive lattice points inside an ellipse

Let Q(u, v) be a positive definite binary quadratic form with arbitrary real coefficients. For large real x, one may ask for the number B(x) of primitive lattice points (integer points (m, n) with gcd(M, n) = 1) in the ellipse disc Q(u, v) x, in particular, for the remainder term R(x) in the asymptotics for B(x). While upper bounds for R(x) depend on zero-free regions of the zeta-function, and thus, in most published results, on the Riemann Hypothesis, the present paper deals with a lower estimate. It is proved that the absolute value or R(x) is, in integral mean, at least a positive constant c time x ^1/4. Furthermore, it is shown how to find an explicit value for c, for each specific given form Q.To Professor Ekkehard Kratzel on his 70th birthday     

On the lattice points on strictly convex surfaces

The aim of this paper is to show that on strictly convex closed surface in the three-dimensional space there cannot be more than $\text{(2.2 + o(1))P}{}^{\mathrm{<mtext>3</mtext><mtext>4</mtext>}}$ points with integral coordinates, where P is the surface area.     

On the number of rational points on a strictly convex curve

Let γ be a bounded convex curve on the plane. Then #(γ ∩ (?/n)²) = o(n ^2/3). This strengthens the classical result due to Jarník [J] (the upper bound cn ^2/3) and disproves the conjecture on the existence of a so-called universal Jarník curve.     

On convex bodies containing a given number of lattice points

Given a convex body K in Euclidean space, a necessary and sufficient condition is established in order that for each n there exists a homothetic copy of K containing exactly n lattice points. Similar theorems are proved for congruent copies of K and for discrete sets other than lattices.     

Random fluctuations of convex domains and lattice points

In this paper, we examine a random version of the lattice point problem. Let denote the class of all homogeneous functions in of degree one, positive away from the origin. Let be a random element of , defined on probability space , and define

for . We prove that, if , where , then

where , the expected volume. That is, on average, . We give explicit examples in which the Gaussian curvature of is small with high probability, and the estimate holds nevertheless.

     

On a plane convex arc with a large number of lattice points

  A convex are on which there are at least M ^{log 2/log 3} rational points of the form (u/M, v/M) is constructed. Bibliography: 10 titles. Translated from Zapiski Nauchnykh Semiriarov POMI, Vol. 357, 2008, pp. 22–32.