On some metric and combinatorial geometric problems

DOI10.1016/0012-365X(86)90009-9MaRDI QIDQ1077726zbMATH OpenOpenAlexFDO

Publication date 1986

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(86)90009-9

combinatorial geometry distances finite point sets in the plane survey

Problem books (00A07) Combinatorial inequalities (05A20) Enumerative combinatorics (05A99) Other combinatorial number theory (11B75) Combinatorial geometries and geometric closure systems (51D20) Convex sets in (2) dimensions (including convex curves) (52A10) Other problems of combinatorial convexity (52A37) Inequalities and extremum problems involving convexity in convex geometry (52A40)

Review text

Most of the problems surveyed are (for obvious reasons) almost as old as the author; almost all are metric and combinatorial, dealing with distances determined by a finite set of points. A sampling of the problems follows. Let \(S\) denote a set of \(n\) points in the plane, \(f(S)\) the number of different distances determined by the (pairs of) points of \(S\), \(g(S)\) the number of times distance 1 is realized, \(f(n)\) the minimum of \(f(S)\) and \(g(n)\) the maximum of \(f(S)\) (max and min taken over all sets \(S\) of \(n\) points). Find \(f(n)\) and \(g(n)\) for small \(n\); find bounds for large \(n\). If \(S\) implements \(f(n)\) (i.e., \(f(S)=f(n))\) must \(S\) have lattice structure? Assuming \(f(S)=o(n)\), must there always be 4 points in \(S\) which determine at most 3 different distances? Suppose \(S\) contains no isosceles triangles; how small can \(f(S)\) be? Assume \(S\) implements \(f(n)\); is it then true that, for every \(k\), \(S\) contains a subset of \(k\) points which implements \(f(k)\)? In particular, must \(S\) contain an equilateral triangle? How many different sets of \(n\) points implement \(f(n)\)? (Two sets are different if they are not related by a similarity transformation.) Let this number be \(r(n)\). \(r(3)=r(5)=1\) while \(r(4)=3\). What about other values? Can one implement \(f(n)\) and \(g(n)\) simultaneously? Certainly yes for small \(n\), but what about all \(n\)? If the points of \(S\) are the vertices of a convex \(n\)-gon, must one of the vertices be such that among the \(n-1\) segments joining it to the others there are at least \([n/2]\) distinct distances? There are many many more problems. Recent progress by Ajtai, Beck, Komlós, Spencer, Szemerédi and others is reported, conjectures are made, prizes are offered. This is another in a series of papers in which the author updates old problems, presents new ones, focuses on directions for new results and continues to influence this area of combinatorics with generosity and ingenuity.

Cites work

Cited in

(46)

This page was built for publication: On some metric and combinatorial geometric problems

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