2017 旭硝子財団 助成研究発表会 要旨集

142/223

空間データ処理における計算困難構造の解明 東京大学大学院総合文化研究科講師 河村彰星 1. 研究の目的と背景 アルゴリズム（機械的手順による計算）の理論は，伝統的には離散的・組合せ的な問題を扱うのを得意としている．すなわち「モノの組合せ方，処理の順番，分類の仕方などの膨大な可能性のうち，最良のものはどれか」という形の問題に対してであれば，どの問題が典型的手法で高速に解けるか，またそうでない問題は如何なる種類の困難さをもつかが，長年にわたり詳しく調べられてきた．そのような理論的知識は，現実の応用問題に有効な計算法の設計にも極めて重要な役割を果している． このため，連続的・図形的な情報に関する計算課題も，よく知られた離散的・組合せ的な問題設定に（時には無理やり）当てはめて理解されてきた面がある．しかし，連続的な空間データが主役となる計算問題では，複数のモノが「一様さ」「滑らかさ」「バランス」といった幾何的な均衡制約の下で関わり合うことで生ずる複雑さが事の本質である場合が多い．その本質を捉える解析手法を整えるため，このような特徴を備えていると思われる基本的な幾つかの問題を最適化の視点から分析した． 2. 研究内容 2.1「遮光」型問題 本テーマに属する素朴な代表的問題としてまず，所与の物体と同じ影を作る（同じ光線に当たる）壁を最小資源で作るという遮光壁（opaque sets）の問題［1］を研究した．例えば二次元平面上で，図1に太線で示すのはいずれも（この平面内の遠くからは）正方形と「同じ形に見える」ような壁である．つまり正方形にぶつかる任意の光線（直線）が，壁にもぶつかるようになっている．この性質をもつ壁は図の左端のように正方形全体を囲めば（或いは二番目のように三方を囲むだけでも）作れるが，より合計長の短い壁でも実現でき，現在知られる最短のものは右端の通りである．正方形という単純な形にもかかわらず複雑な壁が最適となり得るのは，連続的・幾何的な状況のせいである．つまり或る方向の光線を遮るにはそれに直交する向きに壁を置くのが効率的だが，この問題ではあらゆる方向の光線をバランスよく遮る必要があるため，複雑な解が生じ得るのである． 図1正方形と「同じ形に見える」壁とその長さ． これを最適化の視点で解析したいが，まずそもそも非自明な下界（長さ○○未満の壁では不可能であるという限界の立証）を得ることが困難とされていた．これに対し本研究で，従来のコーシー・クロフトン公式による分析を精密化し，50年来の既存の下界を改善する結果を得た［4］．図1の正方形のような特定の図形に限らず，一部の例外を除く一般の形状で同様の下界が得られた（この例外については後日，泉［3］による結果がある）． この解析では，扱う対象が実数データからなることによる難しさを克服する必要があった．壁の断片が幾らでも細かくなり得るために，複数の断片の重なりの量的評価が難しいという困難に，同目的の先行研究は直面していた［1］．これをうまく有限個の断片からなる場合に帰着する新たな論法を考案したのが決め手となった． 非自明な下界を得るという長年の疑問は解決できたが，上界と下界の間になおかなりの開きがある．もとの最適化の目標からすると，現在の近似算法の改善も課題である．なお遮光壁は極めて自然な問題であり様々な変種が考えられる．例えば問題の条件の「直線」を「半直線」に変えると，図形全体（連結とは限らない）を覆い隠す壁を作りたいという問題になる．これは，壁を閉じた囲みに限定すれば最小切断に関する標準的算法で解けるが，一般にはやはり奇妙な形が最適となる場合があり難しい．このようにどこまでが計算可能で，どこから困難性が現れるのか，更なる見極めが将来の課題である． 2.2「警邏」型問題 もう一つの「バランスよく被覆する」型の問題として集中的に扱ったのが警邏（patrolling）である［2］．これは複数の巡査が協力することで，域内のあらゆる地点が必ず一定以内の時間間隔で訪問されることを目標とする問題である（図2のように地点によって異なる頻度−132−発表番号　64〔中間発表〕