最小包含矩形問題 (Minimum bounding rectangle, MBR)
お知らせ
この記事は続きを書くかもしれません.あるいは書かないかもしれません...
Discord で気になるトピックとして挙がったので, 少し考えてみた.
問題 最小包含矩形問題 (Minimum bounding rectangle, MBR)
2次元 Euclid 空間 $\mathbb{E}^2$ 上に 集合 $S$ が与えられたとき,- $S$ を包む面積が最小の長方形 $R$ は存在するのはどのような場合か?
- 長方形は境界も含まれるものとする.
- 点・線分も長方形として認め, その場合は面積0とする.
- 線分・辺は有限の長さを持つものとする.
- 実際にそのような長方形 $R$ を有限の時間内に見つけるアルゴリズムは存在するか?
存在性
$x$ を中心とする半径 $r$ の開円板を $B(x,r)$ と表記する.
定理1 有界でない集合
$S$ を包む長方形は存在するならば, 集合 $\overline{S}$ は有界である.証明 (クリックで展開)
各長方形の頂点のうち, 原点からの距離が最も大きいものの距離を $d$ とすると $\overline{S} \subset B(0, d+1)$ である.
補題2 コンパクト性
$\overline{S}$ を包む長方形が存在するならば $\overline{S}$ はコンパクト.証明 (クリックで展開)
$\mathbb{E}^2$ では有界閉集合とコンパクトは同値であるから, 定理1より $\overline{S}$ はコンパクトである.
補題3 閉包の包含関係
$A\subset B \;\Longrightarrow\; \overline{A} \subset \overline{B}.$証明 (クリックで展開)
$$\begin{align*} A \subset B &\;\Longleftrightarrow\; B^c \subset A^c \\ &\;\Longleftrightarrow\; \operatorname{Int}(B^c) \subset \operatorname{Int}(A^c) \\ &\;\Longleftrightarrow\; \operatorname{Int}(A^c)^c \subset \operatorname{Int}(B^c)^c \\ &\;\Longleftrightarrow\; \overline{A} \subset \overline{B}. \end{align*}$$
定理4 有界な集合
集合 $S$ を包む最小の長方形 $R$ が存在すれば, $R$ は $S$ の閉包 $\overline{S}$ を包む最小の長方形でもある.証明 (クリックで展開)
補題2より, $S \subset R\;\Longleftrightarrow\;\overline{S} \subset \overline{R} = R$ であるから, $R$ は $\overline{S}$ を包む.
また, $R$ より面積の小さい $\overline{S}$ を包む長方形 $R'$ が存在すると仮定すると $S\subset\overline{S}\subset R'$ となり, $R$ が $S$ を包む最小の長方形であることに矛盾.
定理5 長方形の存在条件
次の2条件は同値.- $S$ を包む最小の長方形 $R$ が存在する.
- $S$ は有界.
証明 (クリックで展開)
$S$ が有界であることと $\overline{S}$ が有界であることは同値であるから, (1) $\Longrightarrow$ (2) は容易に示される.
$\pi_x, \pi_y$ をそれぞれ $x$ 座標, $y$ 座標成分の射影とする.
$\pi_x, \pi_y$ は連続であるから $\overline{S}$ のコンパクト性より $\pi_x, \pi_y$ の像は最大値・最小値を持つ. よって, $$[\min_{a\in S}\pi_x(a), \max_{a\in S}\pi_x(a)]\times[\min_{a\in S}\pi_y(a), \max_{a\in S}\pi_y(a)]$$ が辺が $x$ 軸および $y$ 軸に平行なものに限定したときの $S$ を包む最小の長方形である.
$a = (x,y)$ とするとき, $R(\theta,a) = R_\theta(a) = (x\cos\theta - y\sin\theta, x\sin\theta + y\cos\theta)$ は原点を中心に $a$ を $\theta$ 回転させる. 各 $\theta$に対して $R_{\theta}$ はコンパクトであり, $R$ は連続であるから, $R(\theta,a)$ を最小にするような $\theta, a$ が存在する.
ここまでは存在性の話なので, ここからは具体的な長方形の構成について考える. 定理4から閉集合 (閉包) のみを議論すれば十分なので, 以降の $S$ は有界閉集合に限定する.
その他の性質
定理6 凸包
有界閉集合 $S$ を包む最小の長方形 $R$ は凸包 $\operatorname{Conv}(S)$ を包む最小の長方形でもある.証明 (クリックで展開)
$R$ は閉包なので, $S$ 上の任意の2点 $a,b$ を結ぶ線分を含む.
定理7 長方形と凸包の接触
有界閉集合 $S$ を包む最小の長方形 $R$ の各辺 (各端も含む) は凸包 $\operatorname{Conv}(S)$ の境界点を少なくとも1点を含む.証明 (クリックで展開)
辺 $l$が $S$ とどの境界点とも接しないと仮定すると, $S$ の任意の境界点が $l$ から $\varepsilon$ 以上離れているような実数 $\varepsilon >0$ が存在する. しかし辺 $l$ を長方形の重心の方向へ $\varepsilon$ 平行移動しても $S$ を包むので矛盾.
定理8 凸包の境界
$\partial\operatorname{Conv}(S)$ は弧状連結.証明について
GPT 曰くVictor Klee, Some topological properties of convex sets, Trans. Amer. Math. Soc., volume 93, 1959, pp. 52-63
の Klee の定理により示されるらしいが, ネットで調べても該当部分のページが見つからない...
証明できる人いたら教えてください!