駆け足で読む計算幾何学入門 第７章 警備問題

• 美術館問題
  • 多角形内に最小個数の点をとり、多角形内のすべての点が「見える」ようにするための「監視員配置点」を求める問題
  • 美術館定理
  • 単純多角形の三角形への分割
• -
• 警備員巡回路問題
  • 美術館問題では、監視員は不動だったが、１人の監視員が移動してもよいものとして監視するときの巡回最短路問題
  • 巡回セールス問題とことなり、路探索は線形時間で得られる