The number of different distances determined by a set of points in the Euclidean plane

In 1946 P. Erdös posed the problem of determining the minimum numberd(n) of different distances determined by a set ofn points in the Euclidean plane. Erdös provedd(n) cn ^1/2 and conjectured thatd(n)cn/ logn. If true, this inequality is best possible as is shown by the lattice points in the plane. We showd(n)n ^4/5/(logn) ^c .The research of W. T. Trotter was supported in part by the National Science Foundation under DMS 8713994 and DMS 89-02481.     

On the number of rational points of a plane algebraic curve

The number of F_q -rational points of a plane non-singular algebraic curve defined over a finite field F_q is computed, provided that the generic point of is not an inflexion and that is Frobenius non-classical with respect to conics. Received: 18 March 2003     

On the number of primitive lattice points in plane domains

We discuss the error term in the asymptotic formula for the number of integral points with coprime coordinates in star like plane domains assuming the validity of the Riemann Hypothesis.     

On the number of line separations of a finite set in the plane

Let S denote a set of n points in the Euclidean plane. A subset S′ of S is termed a k-set of S if it contains k points and there exists a straight line which has no point of S on it and separates S′ from S?S′. We let f_k(n) denote the maximum number of k-sets which can be realized by a set of n points. This paper studies the asymptotic behaviour of f_k(n) as this function has applications to a number of problems in computational geometry. A lower and an upper bound on f_k(n) is established. Both are nontrivial and improve bounds known before. In particular, $\text{f}{}_{\mathrm{k}}\text{(n) = f}{}_{\mathrm{n?k}}\text{(n) = Ω(n}\text{log}\text{k)}$ is shown by exhibiting special point-sets which realize that many k-sets. In addition, $\text{f}{}_{\mathrm{k}}\text{(n) = f}{}_{\mathrm{n?k}}\text{(n) = O(nk}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ is proved by the study of a combinatorial problem which is of interest in its own right.     

On plane trees with a prescribed number of valency set realizations

We describe valency sets of plane bicolored trees with a prescribed number of realizations by plane trees. Three special types of plane trees are defined: chains, trees of diameter 4, and special trees of diameter 6. We prove that there is a finite number of valency sets that have R realizations as plane trees and do not belong to these special types. The number of edges of such trees is less than or equal to 12R  + 2. The complete lists of valency sets of plane bicolored trees with 1, 2, or 3 realizations are presented. Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 6, pp. 9–17, 2007.     

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.     

On the number of Galois points for a plane curve in positive characteristic,II

For a smooth plane curve , we call a point a Galois point if the point projection at P is a Galois covering. We study Galois points in positive characteristic. We give a complete classification of the Galois group given by a Galois point and estimate the number of Galois points for C in most cases.      

On the number of Galois points for a plane curve in positive characteristic,III

We consider the following problem: For a smooth plane curve C of degree d ≥ 4 in characteristic p > 0, determine the number δ(C) of inner Galois points with respect to C. This problem seems to be open in the case where d ≡ 1 mod p and C is not a Fermat curve F(p ^e  + 1) of degree p ^e  + 1. When p ≠ 2, we completely determine δ(C). If p = 2 (and C is in the open case), then we prove that δ(C) = 0, 1 or d and δ(C) = d only if d−1 is a power of 2, and give an example with δ(C) = d when d = 5. As an application, we characterize a smooth plane curve having both inner and outer Galois points. On the other hand, for Klein quartic curve with suitable coordinates in characteristic two, we prove that the set of outer Galois points coincides with the one of \mathbbF₂{\mathbb{F}_{2}} -rational points in \mathbbP²{\mathbb{P}^{2}}.     

On the algebraic points of a definable set

This paper studies diophantine properties of sets definable in an o-minimal structure over the real field. The main theorem of the author’s recent paper with A. J. Wilkie is refined, and used to deduce a strong result on the density of algebraic points of such sets.      

The maximum size of a convex polygon in a restricted set of points in the plane

Assume we havek points in general position in the plane such that the ratio between the maximum distance of any pair of points to the minimum distance of any pair of points is at mostk, for some positive constant. We show that there exist at leastk ^1/4 of these points which are the vertices of a convex polygon, for some positive constant=(). On the other hand, we show that for every fixed>0, ifk>k(), then there is a set ofk points in the plane for which the above ratio is at most 4k, which does not contain a convex polygon of more thank ^1/3+ vertices.The work of the first author was supported in part by the Allon Fellowship, by the Bat Sheva de Rothschild Foundation, by the Fund for Basic Research administered by the Israel Academy of Sciences, and by the Center for Absorbtion in Science. Work by the second author was supported by the Technion V. P.R. Fund, Grant No. 100-0679. The third author's work was supported by the Natural Sciences and Engineering Research Council, Canada, and the joint project Combinatorial Optimization of the Natural Science and Engineering Research Council (NSERC), Canada, and the German Research Association (Deutsche Forschungsgemeinschaft, SFB 303).     

On the complement of the set of n-collinear points in PG(3, n)

Let ${S = (\mathcal{P}, \mathcal{L}, \mathcal{H})}$ be the finite planar space obtained from the 3-dimensional projective space PG(3, n) of order n by deleting a set of n-collinear points. Then, for every point ${p\in S}$ , the quotient geometry S/p is either a projective plane or a punctured projective plane, and every line of S has size n or n + 1. In this paper, we prove that a finite planar space with lines of size n + 1 ? s and n + 1, (s ≥ 1), and such that for every point ${p\in S}$ , the quotient geometry S/p is either a projective plane of order n or a punctured projective plane of order n, is obtained from PG(3, n) by deleting either a point, or a line or a set of n-collinear points.     

The maximum number of odd integral distances between points in the plane

Four points in the plane with pairwise odd integral distances do not exist. The maximum number of odd distances betweenn points in the plane is proved to ben ²/3+r(r-3)/6 for alln, wherer=1,2,3 andn≡r (mod 3). This solves a recently stated problem of Erdós. Dedicated to Professor Dr. H.-J. Kanold on the occasion of his eightieth birthday