数理解析研究所講究録
第 1799 巻 2012 年 65-66

65

アスペクト比を固定した最小の周囲長方形について

Minimum Enclosing Rectangle with Fixed Aspect Ratio
小林 有 \dag er

堀山 貴史 \d ag er

Tamotsu Kobayashi \dag er

Takashi Horiyama\dager\dag er 埼玉大学工学部\d ag er 埼玉大学理工学研究科\dag er Faculty of Engineering, Saitama University\d ag er Graduate School of Science and Engineering, Saitama University

本研究で扱う問題を直感的に理解するために，以下の問題から論を始める．問題: 一枚の折り紙 (正方形) から，できるだけ大きな正三角形を切り取るには．どのように折り紙を切り取ればよいか．この問題の解は図 1 のようになる．

この問題は次のように一般化できる．凸多角形 とアスペクト比 の長方形 が与えられた時に， と相似な図形で に入れることができる最大のものを求める．この一般化した問題は，次の問題と等しい．凸多角形 とアスペクト比 が与えられた時に， の周囲長方形でアスペクト比 となる面積最小のものを求める．こうした問題は，身の回りの多様な場面で現れる．例えば，コピー用紙や木材などの資材には決められた規格 (アスペクト比) で様々な大きさのものが存在する．切り出したい形が与えられた時に，その周囲長方形でアスペクト比 となる最小のものが求められれば，必要最小限の資材を選択することができ．資材を効率よく活用することができる．慈
$P$

$P$

$R$

$r$

$R$

$P$

$r$

$P$

$r$

$r$

用例にはパッキング問題 [5] や最適レイアウト闘題 [3] がある．
本研究では，回転キャリパー法 [7, 9] に基づく $O(n)$ 時間アルゴリズムを提案する．ここで．

$n$は与えられる凸多角形の頂点の数である．回転キャリパー法は，ノギスの原理によるアルゴリズムの枠組みであり．凸多角形を 2 本の平行線で挟み．その周囲を回転させることで．直径等の幾何的性質を得ることができる．Shamos により凸多角形の直径を求める $o(n)$ 時間アルゴリズム [7]が提案され，Toussaint が回転キャリパー法 [9] と名付けて洗練することで，その後，幅 [6], 面積最小の周囲長方形 [9], 周囲長最小の周囲長方形 [2] などを求める線形時間アルゴリズムが提案されている．また．閉曲線に対して面積最小の周囲長方形を求めるアルゴリズム [4,8] や，2 つの凸多角形の最大距離 [11] や最小距離 [lO] を求めるアルゴリズムなどの発展が知られている．

図 1: 正方形から取れる最大の正三角形

図 2: 正三角形とそれを囲む正方形

66
ここで，例えば面積最小の周囲長方形を求めるアルゴリズムを利用すれば，我々の問題が解決するのだろうか? 冒頭の問題に戻って正三角形に対する面積最小の周囲長方形を求めると．図 2の実線の長方形となる．ここで，我々の問題ではアスペクト比 1 の正方形を求める必要があるため．図 2 の点線のように自然に拡張した正方形を解とすることになる．しかし．上部の余白を活用することで．図 1 の正方形が最適解となる．つまり．アスペクト比を指定された場合には．面積最小で囲むことが最良とは限らない．面積最小の周囲長方形や周囲長最小の周囲長方形を求めるアルゴリズムでは，求める周囲長方形はその一辺が凸多角形 の一辺と共線となるという性質$P$を利用している．

本研究では，アスペクト比 での最小周囲長方形は，その一辺が の一辺と共線となるか まの周囲長方形ではなくなるもの) とたは極小 (すなわち．長辺方向や短辺方向に辺を縮めるとなるかのいずれかとなることを示す．また，この性質を利用した $O(n)$ 時間アルゴリズムを設計する．なお， 点の凸多角形 と 点の凸多角形 が与えられた時に． の相似図形で に入る
$P$

$r$

$\searrow$

$P$

$n$

$P$

$m$

$Q$

$P$

$Q$

$m=4$ の場合が我々の最大のものを求める $O(nm^{2}\log m)$ 時間アルゴリズム [1] が知られており．

問題に対応する．本研究では，これとは異なる回転キャリパー法に基づく．同じ線形時間のアルゴリズムを提案する．

参考文献[1] P.K. Agarwal, N.Amenta and M.Sharir. Largest Placement of One Convex Polygon Inside
Another. Discrete Comput. Geom., 19:95-104, 1998.
[2] A.A.N. DePano. Rotating calipers revisited: optimal polygonal enclosures in optimal time.
In Proc. ACM South Central Regional Conference. 1987.

[3] R.L. Francis and J.A. White. Facihty Layout and Location. Prentice Hall, Rglewood CliffS,NJ, 1974.
[4] H. Freeman and R. Shapira. $Detem\ddot{m}ng$ the minimum-area encasing rectangle for an ar-bitrary closed curve. Comm. ACM, 18:40&413, 1975.

[5] F.C.A. Groen, P.W. Verbeek, N. DeJong, and J.W. Klumper. The smallest box around apackage. Pattem Recogn., $14(1-6):173-178$ , 1981.

[6] M.E. Houle and G.T. Toussaint. Computing the width of a set. IEEE Trans. on Pattem
Analysis and Machine Intelligence, $10(5):761-765$ , 1988.
[7] M.I. Shamos. Computational geometry. $PhD$ thesis, Yale University, 1978.
[8] G.T.Toussaint. Pattern recognition and geometrical $\infty mplexity$. In Proc. 5th International

Conference on Pattem Recognition, pp.1324-1347, 1980.
[9] G.T. Toussaint. Solving geometric problems with the ‘rotating calipers’. In Proc. MELBCOM, 1983.
[10] G.T. Toussaint and B.K. Bhattacharya. Optimal algorithms for computing the minimum
distance between two fimite planar sets. In Proc. 5th International Congress of Cyberneticsand Systems, Mexico City, August 1981.
[11] G.T. Toussaint and J.A. McAlear. A simple $O(n\log n)$ algorithm for finding the maximum
distance between two finite planar sets. Pattem Recognition Letters, 1:21-24, October 1982.