Point sets with distinct distances
type: Item
instance of: scholarly article
title: Point sets with distinct distances
zbMATH Open document ID: 0847.52016
DOI: 10.1007/BF01299744
author: Hanno Lefmann
author: Torsten Thiele
published in: Combinatorica
publication date: 1996-10-08T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 52C10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 806479
zbMATH Keywords: lattice
zbMATH Keywords: distinct distances
zbMATH Keywords: point sets
zbMATH Keywords: efficient algorithm
MaRDI profile type: Publication
cites work: A fast and simple randomized parallel algorithm for the maximal independent set problem
cites work: Extremal uncrowded hypergraphs
cites work: An application of graph theory to additive number theory
cites work: Distinct distances determined by subsets of a point set in space
cites work: Combinatorial complexity bounds for arrangements of curves and spheres
cites work: On some problems of elementary and combinatorial geometry
cites work: Bounds for arrays of dots with distinct slopes or lengths
cites work: The maximum number of unit distances in a convex \(n\)-gon
cites work: Unsolved problems in number theory
cites work: Q3856819
cites work: Repeated angles in the plane and related problems
cites work: Q5186278
cites work: Q3903082
description: scientific article; zbMATH DE number 806479