Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 732.52004
Autor: Avis, David; Erdös, Paul; Pach, János
Title: Distinct distances determined by subsets of a point set in space. (In English)
Source: Comput. Geom. 1, No.1, 1-11 (1991).
Review: Zu p,q in Rd sei D(p,q) ihr euklidischer Abstand. Ist S eine endliche Menge des Rd, so sei D(S) die Menge der verschiedenen Abstände von Punkten p,q in S, p\ne q. Sei nun Nn\subset Rd eine n-elementige Menge und Pk(N) die Menge der k-elementigen Teilmengen von Nn. Ferner sei h in N und damit sei q(Nn,k,h) die Anzahl der k-elementigen Mengen Sk\subset N mit D(Sh) \geq h. Trivial ist q(Nnk,h) \leq \binom{n}{k}. Sei f = f(d,k) die größte Zahl h,derart daß limn ––> oo[q(Nn,k,h)/\binom{n}{k}] = 1 gilt für alle Mengenfolgen (Nn)_{n in N n-elementiger Mengen Nn. f(d,k) ist also die größte Zahl h derart, daß für großes n in fast allen k-elementigen Teilengen einer n-elementigen Menge mindestens h verschiedene Abstände vorkommen.
Das Hauptresultat der Arbeit ist die explizite Bestimmung von f(d,k). Trivial ist f(1,k) = f(2,k) = \binom{k}{2}. Für d \geq 3 ergibt sich zunächst eine explizite obere Schranke g(d,h) aus einem Beispiel von Lenz. Mit Hilfe von graphentheoretischen Methoden wird g(d,k) \geq f(d,k) gezeigt.
Eine Verfeinerung der Problemstellung geht auf Erdös und Purdy zurück: Man finde zu gegebenem i, 0 < i \leq \binom{k}{2} asymptotische Resultate über die maximale Anzahl von k-elementigen Teilmengen Sk n-elementiger Mengen mit D(Sk) \leq i. Für dieses Problem gibt es kaum Ergebnisse. Die Autoren zeigen für den Fall d = 2 das folgende Resultat: Sei k = o(n1/7). Dann haben für genügend großes n fast alle k-elementigen Teilmengen einer n-elementigen Menge \binom{k}{2} verschiedene Abstände.
Reviewer: F.Hering (Dortmund)
Classif.: * 52C10 Erdoes problems and related topics of discrete geometry
Keywords: counting distances
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag