„Bewegungsplanung mit fetten Hindernissen“ von Eva Stöwe (Katzazi@gmx.de) 1   Gliederung 1 GLIEDERUNG ........................................................................ ......................................1 2 MOTIVATION ........................................................................ ......................................2 3 DER BEGRIFF K-FAT........................................................................ ..........................4 3.1 Hypersphäre S m,r ........................................................................ .............................4 3.2 U E ........................................................................ .......................................................4 3.3 k-fat........................................................................ .................................................... 5 3.4 Beispiele verschiedener k-fat Objekte.................................................................... 5 3.5 Eigenschaften der k-Fatness........................................................................ ............6 4 DICHTE EINER K-FAT-UMGEBUNG ....................................................................... 8 4.1 Der minimal umschließende Hypersphären Radius (MES)................................. 8 4.2 Zusammenhang zwischen k-Fatness und Dichte einer Umgebung ..................... 8 5 BEGRIFFE........................................................................ ...........................................10 5.1 Configuration Space........................................................................ .......................10 5.2 C_frei........................................................................ ...................................................10 5.3 Free Cell / Zusammenhangskomponente............................................................. 10 5.4 Einfacher / mehrfacher Kontakt........................................................................ ...10 6 KOMPLEXITÄT VON K-FAT-UMGEBUNGEN ..................................................... 11 6.1 Vorüberlegungen........................................................................ ............................11 6.2 Das Komplexitäts-Theorem........................................................................ ...........12 6.2.1     Annahmen ........................................................................ ....................................12 6.2.2     Theorem ........................................................................ .......................................12 6.2.3     Beweis ........................................................................ ..........................................12 6.3 Bemerkungen........................................................................ ..................................13 7 ERGEBNIS ........................................................................ ..........................................14 8 LITERATURANGABEN ........................................................................ ....................15 Seite 1