The maximum number of unit distances in a convex n-gon
DOI10.1016/0097-3165(90)90074-7zbMATH Open0742.52010DBLPjournals/jct/Furedi90OpenAlexW2007311757WikidataQ64113574 ScholiaQ64113574MaRDI QIDQ1813293FDOQ1813293
Authors: Zoltán Füredi 
Publication date: 25 June 1992
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0097-3165(90)90074-7
Recommendations
- The number of distinct distances from a vertex of a convex polygon
- On unit distances in a convex polygon
- A lower bound on the number of unit distances between the vertices of a convex polygon
- The maximum number of times the same distance can occur among the vertices of a convex \(n\)-gon is \(O(n\log n)\)
- The maximum size of a convex polygon in a restricted set of points in the plane
- The maximum number of unit distances among \(n\) points in dimension four
- A postscript on distances in convex \(n\)-gons
- Maximin distance for \(n\) points in a unit square or a unit circle
- scientific article; zbMATH DE number 800308
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Convex sets in (2) dimensions (including convex curves) (52A10) Erd?s problems and related topics of discrete geometry (52C10)
Cites Work
- On Sets of Distances of n Points
- Extremal problems in discrete geometry
- On some metric and combinatorial geometric problems
- A lower bound on the number of unit distances between the vertices of a convex polygon
- A Problem of Leo Moser About Repeated Distances on the Sphere
- Unit distances
- Some extremal problems in geometry
Cited In (47)
- Large homogeneous submatrices
- The maximum number of times the same distance can occur among the vertices of a convex \(n\)-gon is \(O(n\log n)\)
- On the union complexity of diametral disks
- Degrees of nonlinearity in forbidden 0-1 matrix problems
- Intervertex distances in convex polygons
- An exact characterization of saturation for permutation matrices
- Saturation of Multidimensional 0-1 Matrices
- Almost all permutation matrices have bounded saturation functions
- Computational Geometry Column 34
- Interval minors of complete bipartite graphs
- The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2
- Point sets with distinct distances
- Title not available (Why is that?)
- On linear forbidden submatrices
- Linear bound on extremal functions of some forbidden patterns in 0-1 matrices
- Bounds on parameters of minimally nonlinear patterns
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Convexly independent subsets of Minkowski sums of convex polygons
- Sharper bounds and structural results for minimally nonlinear 0-1 matrices
- Davenport-Schinzel theory of matrices
- On the chromatic number of subsets of the Euclidean plane
- Extremal functions of forbidden multidimensional matrices
- Forbidden formations in multidimensional 0-1 matrices
- On forbidden submatrices
- Linear bounds on matrix extremal functions using visibility hypergraphs
- Title not available (Why is that?)
- The maximum size of a convex polygon in a restricted set of points in the plane
- A postscript on distances in convex \(n\)-gons
- Turán problems for edge-ordered graphs
- Extremal problems for ordered (hyper)graphs: Applications of Davenport-Schinzel sequences
- On 0-1 matrices and small excluded submatrices
- On the structure of matrices avoiding interval-minor patterns
- Partitioning ordered hypergraphs
- Multiplicities of interpoint distances in finite planar sets
- A near-linear algorithm for the planar segment-center problem
- Extremal bounds for pattern avoidance in multidimensional 0-1 matrices
- Sequence saturation
- On unit distances in a convex polygon
- On the chromatic number of disjointness graphs of curves
- Saturation problems about forbidden 0-1 submatrices
- Forbidden paths and cycles in ordered graphs and matrices
- On the number of occurrences of the \(k\)th smallest distance between points in convex position
- Unit distances between vertices of a convex polygon
- Model-based probing strategies for convex polygons
- Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
- Coloring intersection graphs of \(x\)-monotone curves in the plane
- Small distances in convex polygons
This page was built for publication: The maximum number of unit distances in a convex \(n\)-gon
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1813293)
