レベル (計算幾何における) - 版の履歴

2008年11月14日 (金) 00:46にAlbeit-Kunによる

2008-11-14T00:46:12Z

Orsjwiki: "レベル (計算幾何における)" を保護しました。 [edit=sysop:move=sysop]

2007-07-20T00:57:03Z

"レベル (計算幾何における)" を保護しました。 [edit=sysop:move=sysop]

2007年7月11日 (水) 07:56に211.9.146.139による

2007-07-11T07:56:39Z

122.17.2.240: 新しいページ: ''''【れべる (level)】''' $d$次元超平面アレンジメントにおいて, $x_d$軸に平行な直線で貫いたときに下から $k$番目となる交点をもつ...'

2007-07-09T07:54:06Z

新しいページ: ''''【れべる (level)】''' $d$次元超平面アレンジメントにおいて, $x_d$軸に平行な直線で貫いたときに下から $k$番目となる交点をもつ...'

新規ページ

'''【れべる (level)】'''

$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)$時間で求める平面走査法アルゴリズムが知られている.

← 古い版		2008年11月14日 (金) 00:46時点における版
2行目:		2行目:

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

← 古い版		2007年7月11日 (水) 07:56時点における版
1行目:		1行目:
	'''【れべる (level)】'''		'''【れべる (level)】'''

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

← 古い版	2007年7月20日 (金) 00:57時点における版
(相違点なし)