The grid revisited

DOI10.1016/0012-365X(93)90155-MMaRDI QIDQ686463zbMATH OpenWikidataFDO

Authors János Pach, Imre Z. Ruzsa, Zoltán Füredi, P. Erdős

Publication date 22 August 1994

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(93)90155-M

zbMATH Keywords

Erdős problems

Mathematics Subject Classification ID

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

Review text

Diese Arbeit bezieht sich auf die Arbeit von \textit{P. Erdős} [Ann. Math. Mon. 53, 248-250 (1946; Zbl 0060.34805)]. Die originale Fragestellung wurde hier in einer verallgemeinerten Form aufgeschrieben: Sei eine Punktmenge \(P=\{p_1,p_2,\ldots,p_n\}\) in einem metrischen Raum \(M\supseteq P\) gegeben. Die Aufgabe ist die Bestimmung (oder die Abschätzung) des Maximums \(f^M(n)\) des Vorkommens einer gegebenen Entfernung bzw. der kleinsten Zahl \(g^M(n)\) verschiedener Entfernungen in einer Menge \(P\), wobei \(f^M(n) = \max\max_{\alpha>0}\mid\{p_i,p_j\}:d(p_i,p_j)=\alpha|\) bzw. \(g^M(n) = \min\mid\{d(p_i,p_j):1\leq i<j\leq n\}|\) ist. Die Verfasser beweisen die folgenden Sätze: 1. Wenn \(d \geq 4\) und \(n>2\) sind, und \(P\) auf einer Sphäre \(S^{d-1}\) liegt, so existiert immer eine Konstante \(c_d\), womit die folgende Abschätzung \[ g^S(n)= g(P) \leq c_4 {n\over\log\log n} \text{ falls } d=4 \text{ bzw. } g^S(n) = g(P) \leq c_dn^{2/(d-2)} \text{ falls } d>4 \] gilt. 2. Wenn \(n\) eine willkürliche natürliche Zahl ist, so existiert immer eine Konstante \(c\), wobei eine Menge \(P\) aus \(n\) Punkten in der Ebene -- in einer allgemeinen Lage -- so gegeben werden kann, daß die folgende Abschätzung \(g(P)\leq n 2^{c\sqrt{\log n}}\) gilt. 3. Zu jedem \(C>0\) gehört je eine ganze Zahl \(n_0=n_0(C)\) so, daß mindestens \(C_n\) Vektoren in der Ebene durch jede Menge \(P\) aus \(n\) Punkten (in einer allgemeinen Lage) bestimmt werden, falls \(n\geq n_0\) ist. 4. Zu einer willkürlichen Zahl \(\varepsilon>0\) gehört die Zahl \(C=C(\varepsilon)\) mit der folgenden Eigenschaft: Falls die Menge \(P\) der \(C_n\) Punkte auf einem Kreisbereich vom Radius \(n\) eingelagert werden kann, wobei die Entfernungen jeder beiden Punkte nicht kleiner als 1 sind, so -- zu jedem Winkel \(\alpha(0 \leq \alpha \leq 2\pi)\) -- existieren drei Punkte von \(P\), die einen solchen Winkel bestimmen, dessen Größe sich von \(\alpha\) höchstens mit \(\varepsilon\) unterscheidet.

Recommendations

Cites work

Cited in

(19)

This page was built for publication: The grid revisited

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