Kreise und Gitterpunkte

28/02/2008 - 23:08 von Jan Fricke | Report spam
Hallo,
im Zusammenhang mit einer Aufgabe aus de.rec.denksport bin ich auf
folgende Frage gestoßen:

Für einen Punkt x aus dem R^n und r>0 sei M(x,r) die Menge aller Punkte
y aus Z^n mit |x-y|<r. Umgekehrt kann man zu jeder (endlichen) Teilmenge
M von Z^n die Menge R(M) aller Radien r suchen, so dass M=M(x,r) für
irgendein x. Offensichtlich ist R(M) ein Intervall. Was kann man über
dieses Intervall aussagen?

Wenn die Denksport-Aufgabe lösbar ist, dann kann die Intervalllànge
höchstens 1 sein. Es scheint aber so zu sein, dass für größere Radien
die Intervalllànge immer kleiner werden sollte, vermutlich liegt a^n-b^n
maximal in der Größenordnung von 1 für zwei Elemente aus R(M).

Ideen?


Viele Grüße Jan
 

Lesen sie die antworten

#1 Philipp Zumstein
03/03/2008 - 11:44 | Warnen spam
Hallo Jan!

Jan Fricke wrote:
im Zusammenhang mit einer Aufgabe aus de.rec.denksport bin ich auf
folgende Frage gestoßen:

Für einen Punkt x aus dem R^n und r>0 sei M(x,r) die Menge aller Punkte
y aus Z^n mit |x-y|<r. Umgekehrt kann man zu jeder (endlichen) Teilmenge
M von Z^n die Menge R(M) aller Radien r suchen, so dass M=M(x,r) für
irgendein x. Offensichtlich ist R(M) ein Intervall. Was kann man über
dieses Intervall aussagen?



Interessant ist da eigentlich nur die Frage, welches der kleinste Radius
ist, so dass es einen "umschliessenden Kreis" für M gibt. Denn falls
r'>r und es einen umschliessenden Kreis mit Radius r gibt, dann auch
einen mit Radius r'.

Das Problem ist unter den Namen "smallest enclosing ball" bekannt. Eine
Google-Suche gibt da schon einige Treffer (vorallem algorithmische
Aspekte). Hier noch ein spezieller Artikel der als Beitrag zum
Informatik-Jahr eingegangen ist
http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo42.php
Der Artikel richtet sich an eine breite Allgemeinheit und ist daher
verstàndlich und einfach geschrieben.

Aber ich bin mir nicht sicher, ob es nicht in eine andere Richtung geht,
als du eigentlich willst. Darum frage ich einmal hier nach, hilft dir
das oben genannte oder ist das eher "nice-to-know" aber nicht wirklich
hilfreich?


Wenn die Denksport-Aufgabe lösbar ist, dann kann die Intervalllànge
höchstens 1 sein. Es scheint aber so zu sein, dass für größere Radien
die Intervalllànge immer kleiner werden sollte, vermutlich liegt a^n-b^n
maximal in der Größenordnung von 1 für zwei Elemente aus R(M).



Von welcher Aufgabe sprichst du hier?


Grüsse,
Philipp

Ähnliche fragen