This paper is concerned with the problem of estimating \(f_d (n)\), the maximum cardinality of a subset of the \(n^d - \text{grid} \{1,2, \dots, n\}^d\) with distinct mutual distances. Improving results of \textit{P. Erdös} and \textit{R. K. Guy} [Elemente Math. 25, 121-123 (1970; Zbl 0222.10053)] it is proved that \(f_2(n)\geq cn^{2/3}\) and, for \(d\geq 3\), \(f_d(n)\geq c_dn^{2/3}(\ln n)^{1/3}\). Furthermore, any set of \(n\) points in the plane contains a subset with distinct mutual distances of size \(c_1 n^{1/4}\) and for point sets in general position (i.e., no three collinear) of size \(c_2 n^{1/3}\). Finally, an efficient algorithm is given for finding a subset of a given set with desired properties (for example, with distinct distances) of size guaranteed by the probabilistic method.
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- An application of graph theory to additive number theory
- Bounds for arrays of dots with distinct slopes or lengths
- Combinatorial complexity bounds for arrangements of curves and spheres
- Distinct distances determined by subsets of a point set in space
- Extremal uncrowded hypergraphs
- scientific article; zbMATH DE number 3657869 (Why is no real title available?)
- scientific article; zbMATH DE number 3712068 (Why is no real title available?)
- scientific article; zbMATH DE number 3893918 (Why is no real title available?)
- On some problems of elementary and combinatorial geometry
- Repeated angles in the plane and related problems
- The maximum number of unit distances in a convex n-gon
- Unsolved problems in number theory
- On distinct distances among points in general position and other related problems
- Uniform dilations
- Bounds for arrays of dots with distinct slopes or lengths
- Maximal sets of given diameter in the grid and the torus
- On distinct sums and distinct distances.
- Sets of points with pairwise distinct slopes
- On finding maximum-cardinality symmetric subsets
- Circle grids and bipartite graphs of distances
- Selecting a subset of diverse points based on the squared Euclidean distance
- An improved lower bound for general position subset selection
- A note on distinct distance subsets
- Distinct distances between lattice points
- Distinct angles in general position
- scientific article; zbMATH DE number 6700229 (Why is no real title available?)
- WHICH POINT CONFIGURATIONS ARE DETERMINED BY THE DISTRIBUTION OF THEIR PAIRWISE DISTANCES?
- scientific article; zbMATH DE number 4045753 (Why is no real title available?)
- scientific article; zbMATH DE number 1290179 (Why is no real title available?)
- scientific article; zbMATH DE number 1054775 (Why is no real title available?)
- scientific article; zbMATH DE number 2058507 (Why is no real title available?)
- scientific article; zbMATH DE number 1786503 (Why is no real title available?)
- Extreme Distances in Multicolored Point Sets
- Incidences between points and generalized spheres over finite fields and related problems
- Three paths to point placement
- Distinct volume subsets
- Problems on Two-Dimensional Synchronization Patterns
- On the distinct distances determined by a planar point set
- Distinct distances in homogeneous sets
- Distinct angle problems and variants
- The grid revisited
- Distinct distances in planar point sets with forbidden 4-point patterns
- Distinct distances determined by subsets of a point set in space
- On distinct distances and \(\lambda \)-free point sets
This page was built for publication: Point sets with distinct distances
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1900187)
