Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 35 (1994), No. 1, 45-54.

Über die dünnste doppelgitterförmige 2-fache Überdeckung mit einem

zentralsymmetrischen konvexen Bereich

Ágota H. Temesvári

Lehrstuhl für Mathematik, Universität für Forst- und Holzwissenschaft H – 9401 Sopron, Pf. 132, Ungarn

Abstract. Let M be a centro-symmetric convex domain. Denote by D_{1,Γ}(M) the density of the thinnest lattice covering by M. It is shown that the density of the thinnest 2-fold double-lattice covering by M is 2D_{1,Γ}(M). If M is strictly convex, the thinnest 2-fold double-lattice covering is the union of two thinnest lattice coverings. MSC 1991: 52C15

1. Einführung

L. Fejes Tóth [4] hat bewiesen, daß die Überdeckungsdichte von einander nicht kreuzenden kongruenten zentralsymmetrischen konvexen Scheiben nicht kleiner als die Dichte der dünnsten gitterförmigen Überdeckung dieser Scheiben ist. Dumir und Hans-Gill [3] haben gitterförmige 2-fache Überdeckungen mit einem zentralsymmetrischen konvexen Bereich betrachtet. In Verallgemeinerung des Ergebnisses von Blundon [1] für Kreise haben sie gezeigt, daß die Dichte dieser Überdeckungen nicht kleiner als das Doppelte der Dichte der dünnsten gitterförmigen einfachen Überdeckung mit diesem Bereich ist.

In diesem Artikel wird gezeigt, daß auch für die Dichte der doppelgitterförmigen 2fachen Überdeckungen mit einem zentralsymmetrischen konvexen Bereich dasselbe gilt wie im gitterförmigen Fall.

Für Kreise wurde die Richtigkeit dieses Satzes von Temesvári [5] nachgewiesen. Im allgemeinem Fall, d.h. für beliebige 2-fache Überdeckung, gilt aber die obige Feststellung im Hinblick auf das einschlägige Resultat von Danzer [2] nicht. Dieser hat nämlich eine 2-fache Kreisüberdeckung konstruiert, deren Dichte kleiner als das Doppelte der Dichte der dünnsten einfachen Kreisüberdeckung ist.

Supported by Hung. Nat. Found for Sci. Research, grant no.1238 2. Bezeichnungen, grundlegende Begriffe.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}1993 Heldermann Verlag, Berlin

Es sei O ein beliebiger Punkt der Ebene. Wir bezeichnen mit X den Ortsvektor \overrightarrow{OX} und auch seinen Endpunkt. Die von der Geraden XY erzeugte Halbebene, die den Punkt Z enthält, wird mit XY|Z bezeichnet.

Es sei T eine beliebige Punktmenge und X ein beliebiger Vektor. Mit T + Z wird die Punktmenge bezeichnet, die aus T bei der Verschiebung um X hervorgeht. Ein Doppelgitter wird als die Vereinigung der Gitter Γ und Γ + X definiert und mit Σ bezeichnet.

Es sei M ein zentralsymmetrischer konvexer Bereich. Die gitterförmige Anordnung von M ist die Menge M(Γ) := {M + X | X ∈ Γ}, wobei Γ ein vorgegebenes Gitter ist. Entsprechend heißt M(Σ) := {M + X | X ∈ Σ} eine doppelgitterförmige Anordnung von M. Mit M̂ wird die Menge der Randpunkte von M bezeichnet.

Die Mengen M(Γ) bzw. M(Σ) bilden eine k-fache Überdeckung, wenn jeder Punkt der Ebene mit mindestens k der Bereiche von M(Γ) bzw. M(Σ) überdeckt ist. Die Dichte von Bereichsystemen wird bei L. Fejes Tóth [4] ganz allgemein behandelt. In den von uns untersuchten gitterförmigen bzw. doppelgitterförmigen Fällen kann man die Dichte sehr einfach aufschreiben. Es sei T (Γ) der Inhalt des Grundparallelogramms und a(M) der Inhalt des Beriches M. Dann ist die Dichte der Anordnung M(Γ) a(M)/T (Γ), und die Dichte der doppelgitterförmigen Anordnung M(Σ) , Σ = Γ ∪ (Γ + X), ist 2a(M)/T (Γ). Wir bezeichnen mit D_{k,Γ}(M) bzw. D_{k,Σ}(M) das Infimum der Dichten der k-fachen Überdeckungen M(Γ) bzw. M(Σ), d.h. die Dichte der dünnsten gitterförmigen bzw. doppelgitterförmigen k-fachen Überdeckungen mit M.

3. Der Überdeckungssatz

Ehe wir unseren Satz formulieren fügen wir zwei Bemerkungen hinzu, die sich auf den Artikel von Dumir und Hans-Gill [3] beziehen und die beim Beweis des Satzes gebraucht werden.

Bemerkung 3.a. Es sei M(Γ) eine dünnste gitterförmige 2-fache Überdeckung mit dem zentralsymmetrischen konvexen Bereich M. Aus dem Beweis von Dumir und Hans-Gill [3] folgt, daß M(Γ) die Vereinigung von zwei gitterförmigen einfachen Überdeckungen ist. Es sei O der Anfangspunkt des Gitters Γ und der Mittelpunkt von M. Es gibt einen Vektor A, A ∈ Γ, so daß A ⊂ M ist und die Strecke OA keinen weiteren Gitterpunkt enthält. Dieser Vektor wird als Basisvektor von Γ gewählt. Es sei C einer der Schnittpunkte von M̂ und M̂ + 2A (Abbildung 1). (Ist M̂ ∩ M̂ + 2A eine Strecke, dann sei C einer der Endpunkte.)

Die Bereiche M + mA (m = 0, 1, 2) überdecken die Punkte in der Umgebung von C, die mit M + A bedeckt sind, nicht. Folglich existiert ein von A linear unabhängiger Gittervektor B, für den C ∈ M + B und B ein Basisvektor von Γ ist. Es sei Γ_{1} das Gitter mit den Basisvektoren 2A und B. Auf Grund des Vorhergehenden ist M(Γ_{1}) eine einfache Überdeckung.

Bemerkung 3.b. Das Dreieck O(2A)B (Abbildung 1) liegt im Bereich M + C. Im Fall D_{2,Γ}(M)= 2D_{1,Γ}(M) hat dieses Dreieck den maximialen Inhalt unter den in M + C

Abbildung 1

liegenden Dreiecken. Folglich gilt C ∈ M̂ + B. Nach diesen Bemerkungen beweisen wir den folgenden

Satz. Die Dichte einer doppelgitterförmigen 2-fachen Überdeckung der Ebene mit einem zentalsymmetrischen konvexen Bereich M ist nicht kleiner als das Doppelte der Dichte der dünnsten einfachen Überdeckung mit M, d.h., es gilt

D_{2,Σ}(M) = D_{2,Γ}(M) = 2 D_{1,Γ}(M) .

Wenn der Bereich M streng konvex ist, dann kann die Dichte 2D_{1,Γ}(M) nur für die doppelgitterförmigen 2-fachen Überdeckungen realisiert werden, die die Vereinigungen von zwei dünnsten gitterförmigen einfachen Überdeckungen sind.

Beweis. Es sei das Doppelgitter Σ = Γ ∪ (Γ + X) gegeben. Es sei M ein beliebiger zentalsymmetrischer konvexer Bereich, für den M ∈ M(Γ) ist. (Der Anfangspunkt O von Γ möge der Mittelpunkt von M sein.) Dann ist M(Σ) = M(Γ)∪M(Γ+X). Die Definition der Abstandfunktion f(Z) des Bereiches M sei

f(Z) = inf{ϱ | ϱ > 0 Z ∈ ϱM}.

Mit Hilfe dieser Abstandfunktion geben wir die Basisvektoren A und B von Γ folgendermaßen an. Es sei A der Gittervektor, für den f(A) ≤ f(Z), Z ∈ Γ, gilt. Es sei B linear unabhängig von A, und es gelte f(A) ≤ f(B) ≤ f(Z) für jeden von A linear unabhängigen Gittervektor Z von Γ.

Ist die Anordnung M(Γ) eine einfache Überdeckung, dann ist die Behauptung des Satzes offenbar richtig. Falls M(Γ) eine dünnste einfache Überdeckung bildet, dann ist M(Σ) = M(Γ) ∪ M(Γ + X) für einen beliebigen Vektor X eine doppelgitterförmige 2-fache Überdeckung. Ihre Dichte ist D_{2,Σ}(M) = D_{2,Γ}(M) = 2 D_{1,Γ}(M) , folglich tritt die Dichte 2 D_{1,Γ}(M) in unendlich vielen Fällen ein.

Im weiteren nehmen wir an, daß M(Γ) keine Überdeckung ist. In diesem Fall überdeckt M(Γ + X) die von M(Γ) nicht überdeckten Teile der Ebene mindestens zweifach. Folglich existieren solche Teile in der Ebene, die durch M(Γ) mindestens 2-fach überdeckt sind. Wegen der Wahl des Basisvektors A gilt also f(A) < 2.

3.1. Zunächst untersuchen wir den Fall f(B) ≤ 2. Der konvexe Bereich K := M ∩ M + A ist wegen f(A) < 2 nicht leer und ist offenbar zentralsymmetrisch bezüglich \frac{A}{2}. Auch der Bereich L := M ∩M + B ist zentralsymmetrisch und konvex. Es gilt K ∩L = 0, weil M(Γ) keine Überdeckung ist. M und M + A + B bzw. M + A und M + B können natürlich gemeinsame Punkte besitzen.

3.1.1. Ist f(A) ≤ 1, dann liegen die Punkte C := A(\frac{B}{2} ) ∩ O(A + \frac{B}{2} ) und D := O(A − \frac{B}{2} ) ∩ A(−\frac{B}{2} ) in K wegen der Konvexität von M (Abbildung 2), d.h., auch das Parallelogramm OCAD liegt in K. Es sei S := M̂ ∩ (M̂ + B), wobei S im Parallelogramm OA(A + B)B liegen möge.

Abbildung 2

Die durch M(Γ) nicht überdeckten Punkte des Grundparallelogramms OA(A + B)B gehören zum Parallelogramm (\frac{B}{2} )C(A + \frac{B}{2} )(D + B). Dann ist auch M(Σ̄) := M(Γ) ∪ M(Γ + \frac{B}{2} ) eine 2-fache Überdeckung und hat dieselbe Dichte wie M(Σ). M(Σ̄) ist aber eine gitterförmige Überdeckung, ihre Dichte und damit auch die Dichte von M(Σ) ist nicht kleiner als D_{2,Γ}(M).

Wenn der Bereich M und damit auch K streng konvex ist, dann sind die Punkte C und D innere Punkte von K, folglich liegen C und D + B im Inneren von K + \frac{B}{2} . Im Fall f(B) < 2 und f(A) ≤ 1 oder f(B) ≤ 2 und f(A) < 1 kann die Dichte von M(Σ̄) nicht D_{2,Γ}(M) sein, weil M + \frac{B}{2} den Punkt A + \frac{B}{2} als inneren Punkt enthält, d.h., O(A + \frac{B}{2} )B besitzt nicht den maximalen Inhalt unter den in M + \frac{B}{2} liegenden Dreiecken (vgl. Bemerkung 3.a). Die Dichte D_{2,Γ}(M) kann nur im Fall f(A) = 1 und f(B) = 2

Abbildung 3

(Abbildung 3) eintreten. Es läßt sich leicht zeigen, daß M(Σ) = M(Σ̄) in diesem Fall notwendig gilt, d.h., daß M(Σ) eine gitterförmige 2-fache Überdeckung ist.

3.1.2. Es sei 1 ≤ f(A) < 2. Ferner seien P und P_{1} die Schnittpunkte von M̂ und M̂ + A (Abbildung 4). Nehmen wir an, daß der Punkt P im Parallelogramm OA(A + B)B liegt. Es sei R := P_{1}+B. M̂ ∩M̂ + B kann zwei Punkte oder eine Strecke (f(B) = 2) darstellen. Mit S bzw. S_{1} bezeichnen wir diese Schnittpunkte oder die Endpunkte der Strecke. (Im Fall f(B) = 2 kann auch S = S_{1} vorkommen.)

Abbildung 4

Es liege S im Parallelogramm OA(A + B), und es sei Q := S_{1} + A. Das Viereck P QRS ist ein Parallelogramm, weil M zentralsymmetrisch ist. Das Parallelogramm P QRS enthält die Punkte von OA(A + B)B, die von den Bereichen M, M + A, M + A + B, M + B nicht überdeckt werden, weil M konvex ist. Wegen der Konvexität von M folgt auch, daß K und L bzw. K und L + A in derselben durch SP bzw. P Q begrenzten Halbebene liegen. Der Bereich K liegt also in dem Scheitelwinkelraum des Winkels QP S von P QRS. Ebenso kann man einsehen, daß die Bereiche L + A, K + B und L zu je einem äußeren Scheitelwinkelraum von P QRS gehören. Daraus folgt, daß höchstens einer unter diesen vier Bereichen existiert, dessen Translat irgendeinen Punkt des Parallelogramms P QRS überdeckt.

3.1.2.1. Wenn M ∩ (M + A + B) = ∅ und (M + A) ∩ (M + B) = ∅ gelten, dann bilden die mit M(Γ) nicht überdeckten Punkte von OA(A + B)B ein einfach zusammenhängendes Gebiet α. Wir müssen den Bereich α mit M(Γ + X) 2-fach überdecken. Das bedeutet, daß die mit M(Γ) nicht überdeckten Teile der Ebene entweder mit der Verschiebung von K̄ := ∪_{k}(K + kA) oder mit der Verschiebung von L̄ := ∪_{m}(L + mB) überdeckt werden können, wobei k und m ganze Zahlen sind. Deshalb existiert ein Vektor Y, für den K+Y ⊂ M(Γ + X) oder L + Y ⊂ M(Γ + X) gilt und K + Y oder L + Y den Bereich α mindestens 2-fach überdecken.

Abbildung 5

Nehmen wir als erstes an, daß der Bereich K + Y 2-fach überdeckt. K + Y ist konvex und zentralsymmetrisch. Es ist leicht nachzuweisen, daß man auch mit K + \frac{B}{2} das Parallelogramm P QRS überdecken kann. Wir spiegeln nämlich am Mittelpunkt von K + Y (Abbildung 5). Die Bildpunkte von P, Q, R, S werden mit P′, Q′, R′, S′ bezeichnet. Es ist klar, daß K +Y die konvexe Hülle der Punkte P, Q, R, S, P′, Q′, R′, S′ enthält. Dann existiert ein in dieser konvexen Hülle liegendes Translat von P QRS, dessen Mittelpunkt dem Zentrum von K + Y übereinstimmt. Das bedeutet, daß M(Σ̄) := M(Γ) ∪ M(Γ + \frac{B}{2} ) eine 2-fache Überdeckung ist. Es ist offensichtlich, daß M(Σ̄) eine gitterförmige Überdeckung mit M ist, deren Dichte der Dichte unserer ursprünglichen doppelgitterförmigen 2-fachen Überdeckung M(Σ) gleich ist. Die Dichte von M(Σ̄) ist aber größer oder gleich als 2D_{1,Γ}(M) nach Dumir und Hans-Gill [3].

Nehmen wir an, daß M streng konvex ist und M(Σ) die Dichte 2D_{1,Γ}(M) besitzt. In diesem Fall ist auch K streng konvex. Wenn K + Y, Y ≠ \frac{B}{2} das Parallelogramm P QRS enthält, dann liegt mindestens eine Ecke von P QRS im Inneren von K. Folglich liegen alle Ecken P, Q, R, S im Inneren von K + \frac{B}{2} . Die Dichte der gitterförmigen 2-fachen Überdeckung M(Σ̄) := M(Γ) ∪ M(Γ + \frac{B}{2} ) ist auch 2D_{1,Γ}(M). Das Dreieck O(A + \frac{B}{2} )B bzw. A(A + B)(\frac{B}{2} ) liegt in M + S bzw. M + Q und besitzt maximalen Inhalt unter den in M + S bzw. M + Q einbeschriebenen Dreiecken. Nach der Bemerkung 3.b müßten S und Q also Randpunkte von K + \frac{B}{2} sein. Aus dem Vorhergehenden folgt, daß keine doppelgitterförmige 2-fache Überdeckung M(Σ) = M(Γ + Y) ∪ M(Γ), Y ≠ \frac{B}{2} , existiert, deren Dichte 2D_{1,Γ}(M) ist. Nach der Bemerkung 3.a ist M(Σ̄) = M(Γ) ∪ M(Γ + \frac{B}{2} ) die Vereinigung von zwei dünnsten einfachen Überdeckungen.

Ist der Bereich α mit L + Y überdeckt, dann ist analog nachzuweisen, daß M(Σ̄) = M(Γ)∪M(Γ+ \frac{A}{2}) eine gitterförmige 2-fache Überdeckung ist. M(Σ̄) besizt dieselbe Dichte wie M(Σ), d.h., die Dichte von M(Σ) ist ≥ 2D_{1,Γ}(M). Es läßt sich auch zeigen, daß die Dichte 2D_{1,Γ}(M) nur für M(Σ̄) eintritt, wenn M streng konvex ist.

3.1.2.2. Die Überlegungen sind im Fall M ∩ (M + A + B) = ∅ oder im Fall (M + A) ∩ (M + B) = ∅ ganz analog wie in 3.1.2.1.; deshalb wiederholen wir sie nicht.

3.2. Wir haben noch den Fall f(B) > 2 zu untersuchen. Hier ist

(⋃_{m}(M + mA)) ∩ (⋃_{m}(M + B + A)) = ∅,

wobei m eine ganze Zahl ist. Deshalb ist der mit M(Γ) nicht überdeckte Teil der Ebene, der im folgenden mit β bezeichnet wird, in dem durch die Geraden OA und B(A + B) begrentzen Streifen zusammenhängend.

Gilt f(A) ≥ 1, und ist (M + mA) ∩ (M + (m + 2)A) höchstens ein Punkt im Fall f(A) = 1, dann haben die Bereiche K + mA paarweise höchstens einen gemeinsamen Punkt. Das bedeutet aber, daß es kein Translat von ∪_{m}(K + mA) gibt, das die oben erwähnte Punktmenge β 2-fach überdecken würde. Folglich kann M(Σ) keine 2-fache Überdeckung sein.

Nur die Fälle können also vorkommen, in denen f(A) ≤ 1 ist und die Punktmenge (M + mA) ∩ (M + (m + 2)A) mehr als aus einem Punkt besteht. Wir betrachten die Bereiche ∪_{m}(M + mA) und ∪_{m}(M + B + mA), weiterhin die Bereiche von M(Γ + X), deren Zentren im Streifen γ (Abbildung 6) liegen.

Ohne Beschränkung der Allgemeinheit können wir annehmen, daß der Endpunkt des Vektors X im Parallelogramm OA(A + B)B liegt und weiterhin der Abstand des Punktes X von der Geraden OA nicht kleiner als sein Abstand von der Geraden B(A + B) ist. Wir sehen sofort ein, daß die Bereiche ∪_{m}(M + mA) und ∪_{m}(M + X + mA) den durch OA und X(X + A) begrentzen Streifen δ 2-fache überdecken.

Es sei N die Teilmenge von M in der Halbebene OA|X, die mit ∪_{m}(M + mA) genau einfach überdeckt ist. Im Fall N = ∅ gilt offenbar die obige Behauptung. Sonst ist N ein

Abbildung 6

einfach zusammenhängender Bereich, und nur einige der Bereiche von ∪_{m}(M + X + mA) und ∪_{m}(M + X − B + mA) schneiden ihn. Wegen f(B) > 2 gilt

(⋃_{m}(M + X + mA)) ⋂ (⋃_{m}(M + X − B + mA)) = ∅,

folglich ist ∪_{m}(N + mA) ⊂ ∪_{m}(M + X + mA). (Der Fall ∪_{m}(N + mA) ⊂ ∪_{m}(M + X − B + mA) ist offenbar nicht möglich.) Auf ähnliche Weise ist nachzuweisen, daß die mit ∪_{m}(M + X + mA) genau einfach überdeckten Teile der Ebene bereits mit ∪_{m}(M + mA) überdeckt sind.

Gibt es einen solchen Punkt H im Streifen δ, für den H ∉ ∪_{m}(M + mA) und H ∉ ∪_{m}(M + X + mA) ist, dann ist leicht einzusehen, daß auch solche Punkte existieren, die von M(Σ) nicht überdeckt sind. Folglich könnte M(Σ) keine 2-fache Überdeckung sein.

Wir spiegeln den Punkt O an X und bezeichnen sein Spielgebild mit B′. Es sei Γ′ das Gitter mit den Basisvektoren A, B′. Es gilt offenbar T (Γ) ≤ T (Γ′), und das Doppelgitter Σ′ = Γ′ ∪ (Γ′ + X) ist bereits ein Gitter. Aus den obigen Überlegungen folgt, daß M(Σ′) eine 2-fache Überdeckung ist. Die Dichte von M(Σ′) ist 2D_{1,Γ}(M), d.h., es gilt 2\frac{a(M)}{T (Γ)} ≥ 2\frac{a(M)}{T (Γ)} ≥ 2D_{1,Γ}(M).

Es ist nachzuweisen, daß M(Σ) für einen streng konvexen Bereich M nur dann die minimale Dichte 2D_{1,Γ}(M) besitzt, wenn Σ ein Gitter ist.

Damit haben wir den Beweis des Satzes beendet.

Bemerkung 3.c. Es gibt zentralsymmetrische konvexe Bereiche M, die nicht streng konvex sind, und wo eine doppelgitterförmige 2-fache Überdeckung mit M mit der extremalen Dichte D_{2,Σ}(M) existiert, welche jedoch nicht als Vereinigung von zwei gitterförmigen Überdeckungen dargestellt werden kann.

Wir betrachten ein reguläres Achteck D mit Einheitsseiten (Abbildung 7). Seine Ecken werden mit 1, 2 … 8 bezeichnet.

Abbildung 7

Es ist leicht zu beweisen, daß die Ecken eines Dreiecks mit maximalen Inhalt unter den in D einbeschriebenen Dreiecken z.B. die Ecken 1, 4 und als dritte Ecke ein beliebiger Punkt der Seite 67 sind. Der Inhalt dieses Dreiecks ist dem Inhalt des Grundparallelogramms der dünnsten gitterförmigen 2-fachen Überdeckung mit D gleich, d.h., \frac{1}{2}(1 + \sqrt{2})(1 + \frac{\sqrt{2}}{2}). Die Dichte ist also 2 _{\frac{a(D)}{(1+\sqrt{2})(1+ \frac{\sqrt{2}}{2} )}}. Wir geben jetzt eine doppelgit-

terförmige 2-fache Überdeckung mit derselben Dichte an, die man aber als Vereinigung von zwei gitterförmigen Überdeckungen nicht erzeugen kann. Die Basisvektoren A und B von Γ werden folgendermaßen definiert. A und B sind parallel zu je zwei Seiten des Achtecks, und es gelte A ⊥ B, |A| = 1 + \frac{\sqrt{2}}{2} und |B| = 1 + 2 (Abbildung 8). Es sei X parallel zu B und |X| = 1.3 > \frac{|B|}{2}. Die Anordnung M(Σ) := M(Γ)∪M(Γ+X) ist offenbar eine doppelgitterförmige, aber keine gitterförmige 2-fache Überdeckung mit D. Natürlich haben auch andere, sogar unendlich viele doppelgitterförmige 2-fache Überdeckungen mit D die extremale Dichte.

Abbildung 8

Literaturverzeichnis

[1] Blundon, W.J.: Multiple covering of the plane by circles, Mathematika 4 (1957), 7-16.

[2] Danzer, L.: Drei Beispiele zu Lagerungsproblemen, Arch. Math. 11 (1960), 159-165.

[3] Dumir, V.C. and Hans-Gill, R.J.: Lattice double coverings in the plane, Indian J. Pure Appl. Math. 3 (1972), 466-480.

[4] Fejes Tóth, L.: Reguläre Figuren, Akadémiai Kiadó, 1965.

[5] H. Temesvári, Á.: Die dünnste doppelgitterförmige 2-fache Kreisüberdeckung in der Ebene, Studia Sci. Math. Hung. 19 (1984), 285-298.