あれんじめんととは？わかりやすく解説

辞書 類語・対義語辞典 英和・和英辞典 日中中日辞典 日韓韓日辞典 古語辞典

その他の辞書▼
- フランス語辞典
- インドネシア語辞典
- タイ語辞典
- ベトナム語辞典

Weblio 辞書ヘルプ

556の専門辞書や国語辞典百科事典から一度に検索!

無料の翻訳ならWeblio翻訳！

初めての方へ参加元一覧

Weblio 辞書 > 辞書・百科事典 > デジタル大辞泉 > あれんじめんとの意味・解説

デジタル大辞泉

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

アレンジメント【arrangement】

読み方：あれんじめんと

１配置。配列。

２手配。準備。

３編曲。翻案。脚色。

４「フラワーアレンジメント」の略。

「アレンジメント」に似た言葉

» 類語の一覧を見る

編曲アレンジ

OR事典

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

アレンジメント

読み方：あれんじめんと
【英】：arrangement

概要

超平面のアレンジメントとは, 有限個の超平面による空間の分割である. 双対変換によって, 点集合は超平面集合に変換されるので, アレンジメント構造は点集合上の関係構造にも対応する. また, 有向マトロイドの線形な表現でもある. アレンジメントのフェイスの数の数え上げや, 実際にその構造を求めることは, 離散・計算幾何の基礎となっており, ゾーン定理や, $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多面体アレンジメントガブリエルグラフスケルトンスラブ法

>> 「あれんじめんと」を含む用語の索引
あれんじめんとのページへのリンク

辞書ショートカット

1 デジタル大辞泉
2 OR事典

カテゴリ一覧

＋ビジネス

＋業界用語

＋コンピュータ

＋自動車・バイク

＋船

＋建築・不動産

＋ヘルスケア

＋スポーツ

＋辞書・百科事典

すべての辞書の索引

Weblioのサービス

「あれんじめんと」の関連用語

1

colour arrangement デジタル大辞泉

100% |||||

2

アレンジメント デジタル大辞泉

100% |||||

3

通常兵器及び関連汎用品・技術の輸出管理に関するワッセナー・アレンジメント デジタル大辞泉

70% |||||

あれんじめんとのお隣キーワード

あれ‐なり

あれっ‐きり

あれよ‐あれよ

あれんじめんと

あわ‐た・つ

あわ‐よ・い

あわてんぼうのサンタクロース

あわよく‐ば

検索ランキング

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


	(C)Shogakukan Inc. 株式会社小学館
	Copyright (C) 2025 （社）日本オペレーションズ・リサーチ学会 All rights reserved.

ビジネス｜業界用語｜コンピュータ｜電車｜自動車・バイク｜船｜工学｜建築・不動産｜学問
 文化｜生活｜ヘルスケア｜趣味｜スポーツ｜生物｜食品｜人名｜方言｜辞書・百科事典

ご利用にあたって

・Weblio辞書とは

・検索の仕方

・利用規約

・プライバシーポリシー

・サイトマップ

便利な機能

・ウェブリオのアプリ

・画像から探す

お問合せ・ご要望

・お問い合わせ

会社概要

・公式企業ページ

・会社情報

・採用情報

ウェブリオのサービス

・Weblio 辞書

・類語・対義語辞典

・英和辞典・和英辞典

・Weblio翻訳

・日中中日辞典

・日韓韓日辞典

・フランス語辞典

・インドネシア語辞典

・タイ語辞典

・ベトナム語辞典

・古語辞典

・おすすめのプログラミングスクール情報「Livifun」

©2025 GRAS Group, Inc.RSS