安全領域問題
スポンサーリンク
概要
- 論文の詳細を見る
単純な多角形Pを与えたとき、その(幅δの)安全領域(safety zone)Gとは、線分と(半径δの)円弧からなる閉領域で、多角形Pの境界上の点pとGの境界上の点qとのユークリッド距離d(p, q)がδ未満となる点対(p, q)を持たずに多角形Pをかこむ領域のことである。本稿では、任意の単純多角形の最小面積安全領域を線形時間で求めるアルゴリズムを述べる。
- 一般社団法人情報処理学会の論文
- 1999-03-15
単純な多角形Pを与えたとき、その(幅δの)安全領域(safety zone)Gとは、線分と(半径δの)円弧からなる閉領域で、多角形Pの境界上の点pとGの境界上の点qとのユークリッド距離d(p, q)がδ未満となる点対(p, q)を持たずに多角形Pをかこむ領域のことである。本稿では、任意の単純多角形の最小面積安全領域を線形時間で求めるアルゴリズムを述べる。