エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
Solving Manhattan Geometry(1) - agwの日記
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Solving Manhattan Geometry(1) - agwの日記
先日kd-treeについてのエントリを記載したことは、自分にとって計算幾何の面白さを再認識する良い機会と... 先日kd-treeについてのエントリを記載したことは、自分にとって計算幾何の面白さを再認識する良い機会となりました。 計算幾何で用いられる幾何学的アルゴリズムは比較的若く、今でも進化の過程にあります。また、人間には単純に見える問題も計算機にとっては難しかったり、計算量を減らすために様々なアルゴリズムを応用しなければならないというのも特徴として挙げられます。大変面白い分野であると言えます。 さて、今回取り上げるのはマンハッタン幾何です。マンハッタン幾何は計算幾何の一つ、交差問題に属します。その問題の制限から、幾何学的アルゴリズムの中でも初等な問題として取り上げられることが多い様です。この問題は計算幾何の面白さを示す大変良い例であると思います。 さて、マンハッタン幾何は以下の図に示すような水平と垂直の線分によって構成されています。実際にマンハッタンの街路地図がほとんど水平と垂直の線分からなって