A robotok számítási geometriájában és mozgástervezésében a láthatósági gráf a tér pontjainak kölcsönös láthatóságának grafikonja , általában az euklideszi síkon lévő pontok és akadályok halmazára . A gráf bármely csúcsa egy pontot jelent a térben, és bármely él a pontok közötti látóvonalat . Vagyis ha a tér két pontját összekötő egyenes szakasz nem halad át semmilyen akadályon, akkor a gráfban él rajzolódik ki. Ha a térben lévő pontok halmaza egy egyenesen fekszik, akkor ezek rendezett sorozatként értelmezhetők. A láthatósági grafikonok így az idősorelemzés területére is kiterjednek .
A láthatósági grafikonok segítségével megkereshetők a legrövidebb utak a sokszögű akadályok között egy síkban - a legrövidebb út két akadály között egyenes vonalú, és az akadályok csúcsainál fordul, így a legrövidebb út a legrövidebb út a láthatóságban gráf, amelynek csúcsai az akadályok kezdő- és végpontjai, valamint csúcsai [1] [2] . Így a legrövidebb út probléma két egyszerűbb feladatra bontható: láthatósági gráf felépítésére és egy legrövidebb út algoritmusának, például Dijkstra algoritmusának a gráfra történő alkalmazására . Az akadályokhoz képest észrevehető méretű robot mozgásának megtervezéséhez hasonló megközelítés alkalmazható az akadályok növelésével a robot méretének kompenzálására [1] [2] . Lozano-Peretz és Wesley [2] az euklideszi síkon a legrövidebb út láthatósági gráf módszerét Nils Nilsson 1969-es , a Sheka robot mozgásának tervezéséről szóló tanulmányának tulajdonítják, és idézik e módszer 1973-as leírását M. B. Ignatiev orosz matematikusoktól. , F. M. Kulakov és A. M. Pokrovszkij.
A láthatósági grafikonok a rádióantennák helyzetének kiszámítására is használhatók, vagy az építészet és a várostervezés eszközeként a láthatóság elemzésében .
Ha a térpontok halmaza egy egyenesen fekszik, akkor ezek rendezett sorozatként értelmezhetők [3] . Ez a különleges eset hidat épít az idősorok , a dinamikus rendszerek és a gráfelmélet között .
Egy egyszerű sokszög láthatósági grafikonján (azaz oldalak keresztezése nélkül) a csúcsok a térben pontok, a sokszög külső tartománya pedig akadály. Az egyszerű sokszögek láthatósági gráfjainak Hamilton -félenek kell lenniük – a sokszög határa Hamilton-ciklust alkot a láthatósági gráfban. Ismeretes, hogy nem minden láthatósági gráf alkot egy egyszerű sokszöget. Valójában az egyszerű sokszögek láthatósági gráfjai nem rendelkeznek a gráfok egyik osztályának jellemzőivel sem [4] .
A képgaléria probléma egy kis ponthalmaz megtalálásának problémája úgy, hogy az összes többi pont látható legyen a halmaz pontjaiból. A művészeti galéria probléma egyes formái úgy értelmezhetők, hogy egy láthatósági gráfban domináns halmazt találunk.
A sokszögek vagy görbék bitangens rendszerei olyan vonalak, amelyek két sokszöget érintenek. A sokszögek bitangens halmazai a láthatósági gráf egy részhalmazát alkotják, amelynek sokszög csúcsai vannak gráfcsúcsként (térbeli pontok), a sokszögek pedig akadályként szolgálnak. A legrövidebb út megtalálásának problémájának láthatósági gráfja javítható, ha az összes láthatósági él helyett bitangenseket képezünk, mivel a legrövidebb út csak bitangensek mentén haladhat [5] .