arrangementとは - OR事典 Weblio辞書

Weblio 辞書 > 学問 > OR事典 > arrangementの意味・解説

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.

「OR事典」の他の用語

計算幾何：

K-d木 NP困難 TSP多面体アレンジメントガブリエルグラフスケルトンスラブ法

索引トップ用語の索引ランキングカテゴリー

音楽用語辞典

アレンジメント［arrangement］

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

索引トップ用語の索引ランキング

ウィキペディア

編曲

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2011/12/27 09:40 UTC 版)

(arrangement から転送)

編曲（へんきょく、英語: arrangement）は、既存の楽曲において主旋律をそのままに、それ以外の部分に手を加えて、楽曲に幅を持たせる作業の事である。主旋律に手を加える場合は、変奏と呼ぶ。英語表記では「arrangement」「transcription」の2つが用いられるが、「arrangement」の場合は主に、演奏（あるいは音源化）の際に、本来の楽曲のイメージとは異なるイメージを喚起させる目的による改題、編曲を指す。

編曲の作業は往々にして技術的なものだが、編曲者（アレンジャー）の創造的な試みが許されている場であり、時には意外な曲のリバイバルにつながることがある。『展覧会の絵』などはその一例である。

脚注

^ ^a ^b 松浦あゆみ『ブラス＆ストリングスアレンジ自由自在』リットーミュージック、2004年。

[続きの解説]

「編曲」の続きの解説一覧

索引トップ用語の索引ランキングカテゴリー

arrangementに関係した商品

小型水槽のアクセントに！簡単設置！■Plants　Arrangement　ザ　ボンサイ（1個）charm 楽天市場店
生花のアレンジメントオススメですcolor order arrangement-1【ギフト】【送料無料】【楽ギフ_包装】【母の日】グラッシーズ　観葉植物と暮らす
小型水槽のアクセントに！簡単設置！■Plants　Arrangement　ザ　ボンサイ　ver.An.ナナ（1個）charm 楽天市場店

>> 「arrangement」を解説文に含む用語の一覧

>> 「arrangement」を含む用語の索引

>> 「arrangement」を含む用例の一覧

arrangementのページへのリンク

arrangementのページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

1		TPP
2		えずくろしい
3		コシノヒロコ
4		特定非営利活動法人日本フットボールサポーター連盟
5		ベキサロテン
6		ガナッシュ
7		あざとい
8		こざとへん
9		未満
10		屋上屋

11		遡及
12		陳腐化
13		一坪
14		リツイート
15		コシノミチコ
16		捗る
17		ご指導ご鞭撻
18		共益費
19		先負
20		経常利益

21		注意喚起
22		弊社
23		アセスメント
24		福利厚生
25		施策
26		赤口
27		壮行会
28		友引
29		てにをは
30		インセンティブ


	Copyright (C) 2012 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
	Copyright(C) 2000-2012 YAMAHA MUSIC MEDIA CORPORATION. All Rights Reserved. ヤマハミュージックメディア、音楽用語ダス
	All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアの編曲 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

arrangementとは？

OR事典

アレンジメント

概要

詳説

音楽用語辞典

アレンジメント［arrangement］

ウィキペディア

編曲