修士論文 要旨

ベクトル場の丸めによる高精度な整合的デジタル曲線
数理情報学専攻 48-206240
指導教員

吉村 諒
定兼 邦彦 教授とも 1 つ存在する．(prolongation property)

1 概要
画像データやコンピューターディスプレイは [0, n] ×

本研究は，整合的離散化の理論をより一般化した半曲[0, n] 上の n × n グリッドとしてモデル化できる．本論

線群に拡張し，離散化の精度を精密化するものである．

文では各単位正方形 (ピクセル) を格子点と同一視して捉える．このようにした離散平面において，幾何的対象はピクセルの集合として表される．

2 先行研究と本研究の位置づけ
一般の幾何的対象に対してこのような離散化を考え

線分 pq を離散化する愚直な方法として，離散的な xることは困難であるから，まずは一方の端点を固定した座標における線分の y 座標を最も近い整数へと丸める

半直線群 [8, 2, 3]，次に固定を外した線分群 [6, 4, 5]，といったものが考えられるが，これでは公理は満たされそして，端点を固定しある性質を満たすものに限定してない場合がある．図 1 に示したとおり，離散平面に 4半曲線群 [7] を考える研究が主に知られている．

近傍位相が入っているとして，1 点で交わる 2 直線の原点を固定する研究のアイデアは以下のようなもの

離散化の共通部分が複数の連結成分に分かれてしまい，である．デジタル曲線の和集合は全域木をなし，それを不整合が起きる場合がある．

完全に特徴付ける性質から単位正方形 [0, 1]2 上の点集合へとマッピングすることができる．その上で，rangecounting と関わりの深いディスクレパンシーと呼ばれる概念を援用し，ユークリッド曲線と離散化対応物の間の誤差を評価することが可能となる．本研究は [7] の拡張にあたる．
図 1: 1 点で交わる 2 線分の離散化 (赤および青) の共通部分 (紫) が複数の連結成分に分かれる様子

上記研究における CDR の構築法では，ディスクレパンシーの低い特定の点集合をいかなる曲線群に関しても一定して用いているために，グリッドサイズ n に√関して O( n log n) という緩い誤差上界が評価される
このような不整合が起きない離散化として (半直線にとどまっている．本論文では，この問題を曲線群からの) 整合的離散化 (consistent digital rays; CDR)得られるベクトル場の丸め問題として捉え直し，CDRが導入された [8]．整合的離散化は以下のユークリッドの精度とディスクレパンシーとの関連を調べ，表現したの公理に対応する 3 つの性質を満たすものとして定義

い曲線群に関し固有の調整を加えた低ディスクレパンされる：シーな擬似乱数列を構築することで，上記の性質を持つ

定 義 1 (整 合 的 離 散 化). 離 散 化 レ イ の 族 Π=

いかなる曲線群に対しても誤差が O(log1.5 n) であるよ{Π (p) | p ∈ Gn } を考える (Gn はグリッドグラフ

うな CDR が存在すること，および O(log2 n) を達成の三角領域への制限)．この族は以下の 3 条件を満たすするものを多項式時間で構築可能であることを示した．

とき，整合的 であるという：

これは上記の誤差の理論的保証を大きく改善するものである．

(C1) 各 p ∈ Gn に対し，原点 o から p まで唯一の離散化レイ Π (p) が存在する．ただし，Π (o) = {o}とする．(uniqueness property)(C2) q ∈ Π (p) ならば，Π (q) ⊆ Π (p) である．(sub-3 本研究のアイデア
離散化誤差は特定の領域族，点集合の幾何的ディスクレパンシーによって評価される：

segment property)(C3) 各 Π (p) に対し，三角領域の境界にあるピクセ

定義 2 (幾何的ディスクレパンシー). [0, 1]d の部分領

ル r であって，Π (p) ⊆ Π (r) であるものが少なく域族 A と n 点集合 P ⊆ [0, 1]d を考える．組 (P, A)参考文献
を 探索空間 と呼ぶ．集合 vol(A) は A ∈ A なる領域の超体積とする．すると，である．
この変換は，直感的には以下のようになる．まず三角

D(P, A) = |P ∩ A| − n · vol(A) (A ∈ A),

領域 ∆n を固定し，グリッドサイズを倍々にして細かD(P, A) = sup |D(P, A)|,く刻み解像度をあげることによって，半曲線群を十分にA∈A誤差が小さくなるよう近似する．そこから，小さくしたD(n, A) = inf D(P, A)|P |=n誤差をできるだけ保つように気をつけながら，解像度をと し て ，D(P, A) と D(n, A) を そ れ ぞ れ 探 索 空 間粗くしていく．これは，組合せ的ディスクレパンシーが(P, A) および A の 幾何的ディスクレパンシー と呼ぶ．

できるだけ均等な 2 等分を求める問題であることとハ半曲線群には歪領域が対応し，幾何的ディスクレパンシーの定義にはその面積が入っているため，この歪みが問題となる．本研究のアイデアは，これを組合せ的設定 (組合せ的ディスクレパンシー) に持ち込むことで歪みを解消し，以下の補題によって幾何的ディスクレパンシーへと変換するというものである：

イパーエッジ上の点の数の全体に対する比率が離散化誤差に対応するように探索空間を設計していることによる (図 2)．
歪領域の組合せ構造は軸に平行な長方形の族の組合せ構造と完全に同等である．したがって，組合せ構造のみに依存する組合せ的ディスクレパンシーに関しては，軸に平行な長方形の場合に知られている結果を適用

定義 3 (組合せ的ディスクレパンシー). 有限集合 Xできる．このような問題は Tusnády’s problem と呼ばに対して，X と部分集合族 S の組 (X, S) は X 上れ，O(log1.5 n) を達成する彩色の存在，O(log2 n) を達の 集合システム と呼ばれる．これはハイパーグラフ成する彩色の構築手法が知られている [10, 1]．

H = (X, S) を定義する．ハイパーグラフ H の 2 彩色は写像 χ : X → {+1, −1} として表され，集合に対しても χ(S) =∑x∈S χ(x) (S ∈ S) として拡張される．

組合せ的ディスクレパンシー は彩色のバランスを表す指標であり，以下のように定義される：

disc(χ, S) = max |χ(S)|,S∈S

図 2: Transference Principle のイメージ．

disc(S) = min disc(χ, S).
χ

探索空間 (P, A) に対して，A の P 上への制限 A|P ={P ∩ A |A ∈ A} は P 上の集合システムである．これを 組合せ構造 と呼ぶ．これを用いて，領域族 A に対する組合せ的ディスクレパンシーを

参考文献
[1]

[2]

disc(n, A) = max disc(A|P )[3]|P |=nにより定義する．
[4]

補題 4 (Transference Principle [9]). [0, 1] ⊆ A0 な
dる集合 A0 を含む Lebesgue 可測な集合クラスを Aとする．D(n, A) = o(n)(n → ∞) であり，任意[5][6]の自然数 n と固定されたある δ > 0 について，

f (2n) ≤ (2 − δ)f (n) が成り立つような関数 f (n) を用[7]

いて disc(n, A) ≤ f (n) が成り立っているとする．その[8]とき，[9]

D(n, A) = O(f (n))[10]

N. Bansal and S. Garg. “Algorithmic discrepancy beyond
partial coloring”. In: Proc. 49th ACM Symposium on Theory of Computing. 2017, pp. 914–926.
M. K. Chiu and M. Korman. “High dimensional consistentdigital segments”. In: SIAM Journal on Discrete Mathematics 32.4 (2018), pp. 2566–2590.
M. K. Chiu et al. “Distance Bounds for High Dimensional
Consistent Digital Rays and 2-D Partially-Consistent Digital Rays”. In: Proc. 28th European Symposium on Algorithms. 2020, 34:1–34:22.
I. Chowdhury and M. Gibson. “A Characterization of Consistent Digital Line Segments in Z2 ”. In: Proc. 23rd European Symposium on Algorithms. 2015, pp. 337–348.
I. Chowdhury and M. Gibson. “Constructing ConsistentDigital Line Segments”. In: Proc. 12th Latin American
Theoretical Informatics Conference. 2016, pp. 263–274.
T. Christ, D. Pálvölgyi, and M. Stojaković. “Consistent Digital Line Segment”. In: Discrete & Computational Geometry 47-4 (2012), pp. 691–710.
J. Chun, K. Kikuchi, and T. Tokuyama. “Consistent Digital
Curved Rays and Pseudoline Arrangements”. In: Proc. 27thEuropean Symposium on Algorithms. 2019, 32:1–32:16.
J. Chun et al. “Consistent Digital Rays”. In: Discrete &Computational Geometry 42-3 (2009), pp. 359–378.
J. Matoušek. Geometric discrepancy: An illustrated guide.
Springer Science & Business Media, 1999.
A. Nikolov. “Tighter bounds for the discrepancy of boxesand polytopes”. In: Mathematika 63.3 (2017), pp. 1091–1113.