The maximum number of unit distances in a convex \(n\)-gon

DOI10.1016/0097-3165(90)90074-7zbMath0742.52010DBLPjournals/jct/Furedi90OpenAlexW2007311757WikidataQ64113574 ScholiaQ64113574MaRDI QIDQ1813293

Zoltan Fueredi

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

zbMATH Keywords

convex \(n\)-gonmaximum number of unit distances

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Erd?s problems and related topics of discrete geometry (52C10) Convex sets in (2) dimensions (including convex curves) (52A10)

Related Items (42)

An exact characterization of saturation for permutation matrices ⋮ Saturation of Multidimensional 0-1 Matrices ⋮ Almost all permutation matrices have bounded saturation functions ⋮ Multiplicities of interpoint distances in finite planar sets ⋮ Intervertex distances in convex polygons ⋮ Point sets with distinct distances ⋮ Interval Minors of Complete Bipartite Graphs ⋮ Excluded permutation matrices and the Stanley-Wilf conjecture ⋮ Extremal functions of forbidden multidimensional matrices ⋮ On the number of occurrences of the \(k\)th smallest distance between points in convex position ⋮ Small distances in convex polygons ⋮ On the union complexity of diametral disks ⋮ Forbidden formations in multidimensional 0-1 matrices ⋮ Bounds on parameters of minimally nonlinear patterns ⋮ Degrees of nonlinearity in forbidden 0-1 matrix problems ⋮ Turán problems for edge-ordered graphs ⋮ Tight bounds on the maximum size of a set of permutations with bounded VC-dimension ⋮ Sharper bounds and structural results for minimally nonlinear 0-1 matrices ⋮ On the chromatic number of subsets of the Euclidean plane ⋮ Extremal problems for ordered (hyper)graphs: Applications of Davenport-Schinzel sequences ⋮ On unit distances in a convex polygon ⋮ Coloring intersection graphs of \(x\)-monotone curves in the plane ⋮ Davenport-Schinzel theory of matrices ⋮ Forbidden paths and cycles in ordered graphs and matrices ⋮ Unit distances between vertices of a convex polygon ⋮ Model-based probing strategies for convex polygons ⋮ Partitioning ordered hypergraphs ⋮ On forbidden submatrices ⋮ The maximum number of times the same distance can occur among the vertices of a convex \(n\)-gon is \(O(n\log n)\) ⋮ Unnamed Item ⋮ Convexly independent subsets of Minkowski sums of convex polygons ⋮ On the structure of matrices avoiding interval-minor patterns ⋮ Linear bounds on matrix extremal functions using visibility hypergraphs ⋮ On linear forbidden submatrices ⋮ Saturation Problems about Forbidden 0-1 Submatrices ⋮ A near-linear algorithm for the planar segment-center problem ⋮ Linear bound on extremal functions of some forbidden patterns in 0-1 matrices ⋮ On the chromatic number of disjointness graphs of curves ⋮ On 0-1 matrices and small excluded submatrices ⋮ Large Homogeneous Submatrices ⋮ Unnamed Item ⋮ Computational Geometry Column 34

Cites Work

• Extremal problems in discrete geometry
• Unit distances
• 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
• On Sets of Distances of n Points
• Some extremal problems in geometry

This page was built for publication: The maximum number of unit distances in a convex \(n\)-gon