On unit distances in a convex polygon

DOI10.1016/J.DISC.2014.10.009MaRDI QIDQ482205zbMATH OpenOpenAlexFDO

Authors Amol Aggarwal

Publication date 19 December 2014

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1009.2216

zbMATH Keywords

0-1 matrixconvex polygondiagonal propertydistance matrixobtuse angle propertyunit distance

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10)

Abstract: In 1959, ErdH{o}s and Moser asked for the maximum number of unit distances that may be formed among the vertices of a convex $n$-gon; until now, the best known upper bound has been $2pinlo{g}_{2}n+O(n)$, achieved by F"uredi in 1990. In this paper, we examine two properties that any convex polygon must satisfy and use them to prove several new facts related to the question posed by ErdH{o}s and Moser. In particular, we improve on F"uredi's result, and instead obtain a bound of $nlo{g}_{2}n+O(n)$; we exhibit a class of `cycles' formed by unit distances that are forbidden in convex polygons; and we provide a lower bound that shows the limitations of our methods. The second result addresses a question asked by Fishburn and Reeds regarding the possible configurations of vertices that form a convex polygon.

Recommendations

• A lower bound on the number of unit distances between the vertices of a convex polygon
• On distinct distances from a vertex of a convex polygon
• The unit distance problem for centrally symmetric convex polygons
• Unit distances
• Unit distances between vertices of a convex polygon

Cites work

• A lower bound on the number of unit distances between the vertices of a convex polygon
• Forbidden paths and cycles in ordered graphs and matrices
• scientific article; zbMATH DE number 3893918 (Why is no real title available?)
• scientific article; zbMATH DE number 2209719 (Why is no real title available?)
• On 0-1 matrices and small excluded submatrices
• On linear forbidden submatrices
• On Sets of Distances of n Points
• 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 number of unit distances in a convex n-gon
• Unit distances between vertices of a convex polygon

Cited in

(14)

• Unit distances and diameters in Euclidean spaces
• A lower bound on the number of unit distances between the vertices of a convex polygon
• The distance to a polyhedron
• A postscript on distances in convex \(n\)-gons
• The maximum number of unit distances in a convex n-gon
• The unit distance problem for centrally symmetric convex polygons
• Convexly independent subsets of Minkowski sums of convex polygons
• Turán problems for edge-ordered graphs
• Erdős’s Unit Distance Problem
• scientific article; zbMATH DE number 3854463 (Why is no real title available?)
• scientific article; zbMATH DE number 1507557 (Why is no real title available?)
• scientific article; zbMATH DE number 1440118 (Why is no real title available?)
• Forbidden patterns and unit distances
• Unit and distinct distances in typical norms

This page was built for publication: On unit distances in a convex polygon

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q482205)