アレンジメントとは - OR事典 Weblio辞書

Weblio 辞書 > 学問 > OR事典 > アレンジメントの解説

OR事典

アレンジメント

概要

超平面のアレンジメントとは, 有限個の超平面による空間の分割である. 双対変換によって, 点集合は超平面集合に変換されるので, アレンジメント構造は点集合上の関係構造にも対応する. また, 有向マトロイドの線形な表現でもある. アレンジメントのフェイスの数の数え上げや, 実際にその構造を求めることは, 離散・計算幾何の基礎となっており, ゾーン定理や, $k \,$ -集合に関係するレベルなど種々の有用な定理が知られている.

詳説

超平面のアレンジメント(hyperplane arrangement) とは, 超平面による空間の分割である. 双対変換によって, 点集合は超平面集合に変換されるので, 点集合の問題にも対応する. また, 離散システムの観点からは, 線形有向マトロイドの1つの表現である. 組合せ幾何とアルゴリズムからの詳しい解説が [1] にある.

$d\,$ 次元ユークリッド空間 ${\mathbf R}^d\,$ 内の $n\,$ 個の超平面( $d=2\, \,$ の場合は直線) の集合 $H\,$ を考える. この $H\,$ によって, ${\mathbf R}^d\,$ はいろいろな次元のフェイス (face) に分割される. 例えば, 2次元内の有限個の直線の集合は, 2次元, 1次元, 0次元のフェイス (面, 辺, 点) に平面を自然に分割する. これらのフェイスの集合とその接続関係, 各フェイスに対しそれを含む超平面の情報を合わせたものを $H\,$ のアレンジメントといい, ${\mathcal A}(H)\,$ と書く. フェイスの次元を明記したいときは, $k\,$ 次元 $(0 \le k\le d)\,$ のフェイスを $k\,$ -フェイスと書く. $0\,$ -フェイスを頂点, $1\,$ -フェイスを辺, $(d-1)\,$ -フェイスをファセット (facet), $d\,$ -フェイスをセル (cell) とも呼ぶ.

フェイス $f\,$ がフェイス $g\,$ の部分フェイスであるとは, $f\,$ の次元が $g\,$ の次元より1だけ小さく, $f\,$ が $g\,$ の境界に含まれていることである. $f\,$ が $g\,$ の部分フェイスならば, $f\,$ と $g\,$ は (互いに) 接続しているといい, この関係を接続関係という. フェイスの接続関係全体は束をなし, アレンジメントは, 各フェイスの座標など幾何情報と, このフェイスのなす束で表される.

${\mathbf R}^d\,$ 内の $n\ge d\,$ 個の超平面のアレンジメントが単純 (simple) であるとは, $H\,$ に属する任意の $d\,$ 個の超平面は1点で交わり, どの $d+1\,$ 個の超平面も共通の交点をもたないことである. アレンジメントの $k\,$ -フェイスの最大数 $f_k(H)\,$ は, アレンジメントが単純であるとき達成され,

$f_k(H)=\sum_{i=0}^k {d-i\choose k-i}{n\choose d-i}\,$

で与えられる. 特に, $d\,$ -フェイス, すなわちセルの数は $d\,$ を定数とみなすと $\textstyle f_d(H) ={\sum}_{i=0}^d {n\choose d-i}={\rm O}(n^d)\,$ となる.

アレンジメントは逐次添加法で構成できる. 超平面を1つずつ付け加え, アレンジメントの接続関係を更新していく方法である. 2次元の場合で, 平面上の $n\,$ 本の直線からなる単純なアレンジメントを構成する方法を述べる. $n\,$ 本の直線の集合を $L=\{ l_1,l_2,\cdots ,l_n\}\,$ とし, $(x,y)\,$ 平面上にあるとする. $k-1\,$ 本の直線 $l_1,\cdots ,l_{k-1}\,$ からなるアレンジメントに $k\,$ 番目の直線 $l_k\,$ を加えてアレンジメントを更新する. 各頂点には, この頂点に接続している4つの辺を反時計回りの順で貯えておく. 各辺には, その辺を含む直線の式と辺の両端点の頂点を覚えておく. $x=-\infty\,$ で $l_k\,$ のすぐ上にある直線を左から辿り, この辺の下に接続している面の境界を時計回りに回って行く. $l_k\,$ と交わった時は, その交点から始めて, 今度は隣の面の境界を時計回りに辿る. これを $l_k\,$ がすでにアレンジメントに存在していた $k-1\,$ 本の直線と交わるまで行なう. この操作により, $l_k\,$ 上に新たに現れる頂点もすべて列挙することができ, そこでアレンジメントを更新していくことができる. その手間は, 直線 $l_k\,$ と交わる面の境界上で辿る辺の数に比例する.

$d\,$ 次元の $n\,$ 個の超平面のアレンジメントにおいて, 新たに1つ超平面 $h\,$ を加え, $h\,$ と交わる各セルのフェイスの集合をゾーンと定義すると, 次のゾーン定理が成り立つ.

ゾーン定理. $d\,$ 次元空間内の $n\,$ 個の超平面から成るアレンジメントにおいて, 1つの超平面のゾーンのフェイスの総数は ${\rm O}(n^{d-1})\,$ である.

このゾーン定理より, アレンジメントを逐次添加法で構成したときの計算量を ${\rm O}(n^d)\,$ でおさえることができる.

ゾーン定理の離散幾何への応用を1つ上げておく. $d\,$ 次元の $n\,$ 超平面のアレンジメントのセルの集合を ${\mathcal C}\,$ , 各セル $c\in {\mathcal C}\,$ のファセットの数を $d(c)\,$ としたとき, $\textstyle {\sum}_{c\in{\mathcal C}}d(c)^2={\rm O}(n^d)\,$ が成り立つ. $\textstyle {\sum}_{c\in{\mathcal C}}d(c)={\rm O}(n^d)\,$ であるから, 各セルのファセットの数はそんなに分散が大きくないことがわかる. 2次元の場合には, このような関係から複数のセルの辺の数を評価することができる.

$d\,$ 次元超平面アレンジメントにおいて, $x_d\,$ 軸に平行な直線で貫いたときに下から $k\,$ 番目となる交点をもつフェイス全体の集合を $k\,$ -レベル, または単にレベルという. 2次元の場合, 高々 $k\,$ までのレベルのサイズは ${\rm O}(kn)\,$ であり, $k\,$ -レベルのサイズは ${\rm O}(\sqrt{k}n)\,$ となる. 双対性より, これは平面の $n\,$ 点を直線で等分割する方法の数が ${\rm O}(n^{1.5})\,$ であることも意味する. $k\,$ -レベルを ${\rm O}(\sqrt{k}n(\log n)^2)\,$ 時間で求める平面走査法アルゴリズムが知られている.

3次元の平面のアレンジメントでもレベルのサイズは ${\rm o}(n^3)\,$ である. 4次元以上の場合, 全体より小さいオーダであるかどうかはわかっていない. また, 高次元の場合は, 0, 1次元フェイスの頂点, 辺で構成されるスケルトンをたどるアルゴリズムも知られており, 特に3次元ではアレンジメント全体を求めるよりも効率よく計算できる. レベルや1つのセルのスケルトンも有用で, 点集合の問題を双対変換して解いている場合, スケルトンのみで十分な場合もある.

曲線・曲面のアレンジメントも有用であり, このアレンジメントの1つのセルやゾーンの組合せ複雑度の解析は, Davenport-Schinzel列の理論としてまとめられている. 定数次数の代数曲線のアレンジメントでは, セルのフェイス数は一般次元で全体のオーダよりほぼ1つ小さな次数の数でおさえられる.

参考文献

[1] H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987. 邦訳 (今井浩, 今井桂子訳), 『組合せ幾何学のアルゴリズム』, 共立出版, 1995.

辞書の索引用語の索引ランキング

音楽用語辞典

アレンジメント［arrangement］

編曲のこと。普通アレンジと略して言われている。一般的にはあるメロディをもとに、数種の楽器で演奏して全体がひとつの音楽になるように譜面を書く作業のこと。同じメロディでもバンド編成、作りたい音楽のムード（ラテン的に、クラシック的に……etc.）によってその聞こえ方は大きく変わってしまうため、アレンジメント（アレンジャー）の役割は非常に重要。

辞書の索引用語の索引ランキング

1		松岡大介
2		リツイート
3		新 QC７つ道具
4		先勝
5		黄砂
6		WiFi
7		攘夷
8		年収
9		続柄
10		ゆうゆう窓口

11		友引
12		QC7つ道具
13		経常利益
14		赤口
15		植松真美
16		弊社
17		執行役員
18		白太刀
19		新QC７つ道具
20		長江崚行

21		以下
22		コンプライアンス
23		営業利益
24		離職票
25		共益費
26		役職
27		.m4a
28		親和図法
29		風速
30		未満


	Copyright (C) 2010 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
	Copyright(C) 2000-2010 YAMAHA MUSIC MEDIA CORPORATION. All Rights Reserved. ヤマハミュージックメディア、音楽用語ダス

アレンジメントとは？

OR事典

アレンジメント

概要

詳説

音楽用語辞典

アレンジメント［arrangement］