Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  831.52009
Autor:  Erdös, Paul; Fishburn, Peter
Title:  Intervertex distances in convex polygons. (In English)
Source:  Discrete Appl. Math. 60, No.1-3, 149-158 (1995).
Review:  Let V be the set of vertices of a convex n-gon in the plane. Denote by d1, ..., dm the different positive distances between the points of V, and by rk the multiplicity of dk. Choose the numbering such that r1 \geq r2 \geq ··· \geq rm. For fixed n, the maximum of ri over all convex n-gons is denoted by ri (n). The values of r1 (n) and r2 (n) are known for n \leq 8. In particular we have r2 (n) \leq n in this case. Here a construction is presented which shows r2 (25) \geq 26 and \supn r2 (n)/n \geq 7/6.
A monotone sequence in V from v0 is a sequence of vertices v0, v1, ..., vk in which the vi are encountered in succession going (counter-)clockwise from v0, such that the distance from v0 to vi is strictly increasing. Let g(n) denote the minimum (over all convex n-gons) of the maximum length of monotone sequences. In a previous paper, the authors have shown \lfloor n/3 \rfloor+1 \leq g(n). Here, g(n) \leq \lceil n/3 \rceil+2 is proved.
Reviewer:  J.Linhart (Salzburg)
Classif.:  * 52C10 Erdoes problems and related topics of discrete geometry
Keywords:  minimum number of different distances; multiplicity vector

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page