複合長方形領域の最小分割

Hiro Ono / 小野雅裕 @masahiro_ono

数学に強い方、ヘルプ要請です!!!! 以下の問題を解くアルゴリズムを探してます。(Pythonライブラリがあればなお良い。)ご存知でしたら教えて下さい！ 問題：バイナリ値（0か1）が入った2Dグリッドが与えられたとき、最少の数の長方形で1のセルを全て覆い、かつ0のセルを全く覆わない方法を見つける。 pic.twitter.com/e7kbqHj41X

拡大

Hiro Ono / 小野雅裕 @masahiro_ono

きっと解いた人がいるであろうこの問題が、何と呼ばれているかだけでも教えていただければ嬉しいですm(_ _)m

Hiro Ono / 小野雅裕 @masahiro_ono

みなさま、たくさんのレスありがとうございます！！！友人が見つけてくれた解法も貼っておきます！ 結論からいうとNP hardで、どうやって近似的に解くかがフォーカスです。 en.wikipedia.org/wiki/Polygon_p… github.com/mittalgovind/P… stackoverflow.com/questions/5919…

素地 @50j1_

@masahiro_ono 最大長方形問題というものがあり(algorithms.blog55.fc2.com/blog-entry-133…)、これを繰り返し適用することで(最大長方形を検出→埋めるの繰り返し)、O(領域の面積×長方形の分割数)の計算量で実現可能な気はします、、(もっと賢いやり方がある気もします…)

hhk @hkorg

@masahiro_ono 最大の長方形であれば、以下が参考になると思います。最大が見つかれば、それを除いて同様のアルゴリズムで次の最大が見つかるはず。 ipsj.or.jp/07editj/promen…

宇宙ツイッタラーX @kenkoooo

@masahiro_ono Python3 での実装例です。 ideone.com/zmA3a2

Tatt (たっと) @tatt61880

@50j1_ @masahiro_ono その方法では添付画像のInputに対し3つの長方形が必要になると思うのですが違いますか？ pic.twitter.com/g7nvt6kvBq

拡大

Yotaro Takazawa @y_takazawa

@masahiro_ono Imai and Asano, SIAM J. Comput. (1986)の7.1にほぼ同じ問題（より一般的？）が載ってますがどうでしょうか。 問題を二部グラフ上の独立集合問題にして帰着して解いているみたいで、実装も楽かと思いました。 semanticscholar.org/paper/Efficien…

Yotaro Takazawa @y_takazawa

@masahiro_ono 具体的には、 1. 論文の通りに二部グラフ上の独立集合問題に帰着する。 2. 二部グラフ上の最大独立集合は、二部グラフの最大マッチングから間接的に求まるので、Pythonの最大マッチングのライブラリ（Networkxなど)を使って求める という感じでいけるかなと 参考slideshare.net/mobile/drken12…

Tatt (たっと) @tatt61880

@hkorg @masahiro_ono その方法では添付した画像のInputで3つの長方形を使用することになると思うのでダメだと思います。(2つの長方形で済みます。) pic.twitter.com/lm5f6p1y5W

拡大

not @not_522

ICPC2012国内予選G ACM洋菓子店 twitter.com/masahiro_ono/s…

百千万億 萬 @TumoiYorozu

@masahiro_ono ci.nii.ac.jp/naid/110002723…

Hiro Ono / 小野雅裕 @masahiro_ono

あ、ちなみに、詳細は省きますが、この問題が解けたら火星ローバーのなにかしらんに役立ったりします！ twitter.com/masahiro_ono/s…