Graf viditelnosti - Visibility graph

v výpočetní geometrie a robot plánování pohybu, a graf viditelnosti je graf neviditelných míst, obvykle pro soubor bodů a překážek v Euklidovské letadlo. Každý uzel v grafu představuje umístění bodu a každý okraj představuje a viditelné spojení mezi nimi. To znamená, že pokud úsečka spojující dvě místa neprochází žádnou překážkou, je mezi nimi v grafu nakreslena hrana. Když sada pozic leží v řadě, lze to chápat jako uspořádanou sérii. Grafy viditelnosti byly proto rozšířeny do oblasti časové řady analýza.

Aplikace

K vyhledání lze použít grafy viditelnosti Euklidovské nejkratší cesty mezi množinou polygonální překážky v rovině: nejkratší dráha mezi dvěma překážkami sleduje přímé úseky, s výjimkou vrcholy překážek, kde se může otočit, takže euklidovská nejkratší cesta je nejkratší cesta v grafu viditelnosti, která má jako uzly počáteční a cílový bod a vrcholy překážek.[1] Euklidovský problém s nejkratší cestou lze proto rozložit na dva jednodušší dílčí problémy: konstrukci grafu viditelnosti a použití algoritmu nejkratší cesty, jako je například Dijkstrův algoritmus do grafu. Pro plánování pohybu robota, který má nezanedbatelnou velikost ve srovnání s překážkami, lze použít podobný přístup po rozšíření překážek, aby se vyrovnala velikost robota.[1] Lozano-Pérez a Wesley (1979) připisuje metodu grafu viditelnosti pro euklidovské nejkratší cesty výzkumu v roce 1969 Nils Nilsson o plánování pohybu pro Zatřesený robot, a také citovat popis této metody z roku 1973 ruskými matematiky M. B. Ignat'yevem, F. M. Kulakovem a A. M. Pokrovským.

K výpočtu umístění lze také použít grafy viditelnosti rádiové antény, nebo jako nástroj používaný v rámci architektura a územní plánování přes analýza grafu viditelnosti.

Graf viditelnosti sady míst, která leží v řadě, lze interpretovat jako graficko-teoretické znázornění časové řady.[2] Tento konkrétní případ staví most mezi časové řady, dynamické systémy a teorie grafů.

Charakterizace

Graf viditelnosti a jednoduchý mnohoúhelník má vrcholy polygonu jako umístění bodů a vnější část polygonu jako jediná překážka. Grafy viditelnosti jednoduchých polygonů musí být Hamiltonovské grafy: hranice polygonu tvoří v grafu viditelnosti hamiltonovský cyklus. Je známo, že ne všechny grafy viditelnosti indukují jednoduchý mnohoúhelník. Ve skutečnosti grafy viditelnosti jednoduchých polygonů nemají vlastnosti několika speciálních tříd grafů.[3]

Související problémy

The problém s uměleckou galerií je problém najít malou sadu bodů tak, aby z této sady byly viditelné všechny ostatní body bez překážek. Určité formy problému umělecké galerie lze interpretovat jako nalezení a dominující sada v grafu viditelnosti.

The bitangenty systému mnohoúhelníků nebo křivek jsou čáry, které se dotýkají dvou z nich, aniž by je pronikly v místech dotyku. Bitangenty sady polygonů tvoří podmnožinu grafu viditelnosti, která má jako uzly vrcholy polygonu a samotné polygony jako překážky. Přístup grafu viditelnosti k problému s euklidovskou nejkratší cestou lze urychlit vytvořením grafu z bitangens namísto použití všech hran viditelnosti, protože euklidovská nejkratší cesta může pouze vstoupit nebo opustit hranici překážky podél bitangenta.[4]

Viz také

Poznámky

  1. ^ A b de Berg a kol. (2000), oddíly 5.1 a 5.3; Lozano-Pérez a Wesley (1979).
  2. ^ Lacasa, Lucas; Luque, Bartolo; Ballesteros, Fernando; Luque, Jordi; Nuño, Juan Carlos (2008). „Od časové řady po složité sítě: graf viditelnosti“. Sborník Národní akademie věd. 105 (13): 4972–4975. arXiv:0810.0920. doi:10.1073 / pnas.0709247105. PMC  2278201. PMID  18362361.
  3. ^ Ghosh, S. K. (01.03.1997). „Rozpoznávání a charakterizace grafů viditelnosti jednoduchých polygonů“. Diskrétní a výpočetní geometrie. 17 (2): 143–162. doi:10.1007 / BF02770871. ISSN  0179-5376.
  4. ^ de Berg a kol. (2000), str. 316.

Reference

externí odkazy