| |
„Bewegungsplanung mit fetten Hindernissen“ von Eva Stöwe (Katzazi@gmx.de)
4 Dichte einer k-fat-Umgebung
Jetzt wo wir ein „Kompaktheits“-Maß, die k-Fatness haben, können wir uns überlegen,
welche Auswirkungen es hat, wenn wir eine Umgebung nur mit k-fat-Hindernissen für einen
ebenfalls k-fat-Roboter haben. Wie einleitend erwähnt wäre es schön, wenn durch diese k-
Fatness die Dichte dieser Umgebung, also die Zahl der Objekte, die innerhalb eines
bestimmten Raumes (z.B. in der Reichweite des Roboters) liegen können, klein ist.
Wenn wir uns allerdings noch einmal an die Anfangsüberlegungen erinnern, ist nicht nur die
k-Fatness der Objekte selbst, sondern auch das Größenverhältnis zwischen dem Roboter und
den Hindernissen relevant. Daher brauchen wir noch ein Maß für die Größe von Objekten.
4.1 Der minimal umschliesende Hyperspharen Radius (MES)
Definition 4:
Der minimal umschließende Hypersphären Radius (MES) eines Objektes E, ist der Radius
der kleinsten Hypersphäre, die E ganz enthält.
Im 2-dimensionalen ist die minimal umschließende
Hypersphäre eines Objektes E der Umkreis um dieses Objekt,
die 3-dimensionalen die Umkugel. Der MES ist demnach der
Radius des Umkreises bzw. der Umkugel.
Es gibt auch alternative Ansätze zur Bestimmung der
Größe eines Objektes, z.B. über das Volumen (der
Hypersphäre). Da Radius und Volumen aber voneinander
Abhängig sind, und der Radius, egal in welcher
Ausgangsdimension wir uns befinden, immer einheitlich
eindimensional ist, haben wir den MES als Maß gewählt.
MES
E
4.2 Zusammenhang zwischen k-Fatness und Dichte einer Umgebung
Theorem 1:
Sei k 1, c 0 und eine Menge sich nicht berührender k-fat-Objekte in d mit
ÍE MESE p.
Dann ist die Anzahl der Objekte E , innerhalb jeder Region R mit MESR=c*p begrenzt
durch
k*(c+1)d.
Beweis:
Idee: Wähle eine Region T, so dass jedes E, das R schneidet, ein bestimmtes minimales
Volumen in T hat. Da sich die Objekte jeweils nicht überschneiden kann man dann dieses
Volumen mit dem Volumen von T vergleichen und erhält eine obere Schranke der Anzahl der
Objekte in R:
Zur Bestimmung der Region T bilden wir zuerst den d-dimensionalen „Umkreis“ um die
Region R. Dieser habe den Mittelpunkt O. Sein Radius entspricht dem MESR ist also c*p. Wir
erhalten nun T, indem wir den Radius um p verlängern. T ist also die Hypersphäre SO,c*p+p.
Seite 8
|  |
|
| |
|
|
