MIMS 現象数理学研究拠点共同研究集会


幾何的解析と形状表現の数理

アブストラクト集
２０１８年８月２４日（金）・２５日（土）明治大学 中野キャンパス６階 研究セミナー室３（６０３号室）

主催：明治大学先端数理科学インスティテュート「現象数理学研究拠点」
プログラム8月24日（金）［会場：6階 研究セミナー室3］
13:30 〜 14:20○ 森口 昌樹（明治大学 先端数理科学インスティテュート）1

14:20 〜 15:10○ 室谷 浩平（公益財団法人 鉄道総合技術研究所）
2

15:20 〜 16:10

粒子法のためのポリゴンと粒子の混合境界表現○ 山本 修身（名城大学）
3

16:10 〜 17:00

視体積交差法と錯視立体

剰余類を用いた魔方陣の効率的な数え上げについて○ 今堀 慎治（中央大学 理工学部 情報工学科）
4

実社会で生じる図形配置問題に対するアルゴリズム設計

8月25日（土）［会場：6階 研究セミナー室3］

10:00 〜 10:50○ 長井 超慧（東京大学大学院工学系研究科 精密工学専攻）
5

産業応用に向けた形状処理技術○ Supanut Chaidee (Department of Mathematics, Faculty of Science, Chiang Mai Univ.),
Kokichi Sugihara (Meiji Institute for Advanced Study of Mathematical Sciences, Meiji Univ.)

10:50 〜 11:40
6

12:50 〜 13:40

Spherical Laguerre Voronoi Diagram as a Tool for
Modeling the Spherical Tessellations○ 今井 敏行（和歌山大学 システム工学部）
7

幾何処理で正確であってほしい情報と近似算法○ 谷口 隆晴（神戸大学大学院システム情報学研究科，JST さきがけ），
小松 瑞果（神戸大学大学院システム情報学研究科），
13:40 〜 14:30
大川 剛直（神戸大学大学院システム情報学研究科，JST CREST）
8

14:40 〜 15:30

情報幾何学を用いた発展型ネットワークモデルに基づく相転移に着目した
異常検知の試み○ 杉原 厚吉（明治大学 先端数理科学インスティテュート）9

脳の直角優先性を利用した多義立体の設計法

視体積交差法と錯視立体
森口 昌樹（明治大学 先端数理科学インスティテュート）
視体積交差法とは，複数の 2 次元図形（3 次元形状の輪郭を表している）から 3 次元形状を構築するための基本的手法である．このとき，それぞれの 2 次元図形に対応する視点情報も与えられているものとする．
この手法は，はじめにそれぞれの 2 次元図形を逆投影して掃引体を計算し，それから全ての掃引体に含まれる形状を抽出する．抽出された形状は視体積交差メッシュと呼ばれる．入力図形が適切な条件を満たせば，視体積交差メッシュを指定された視点から観察すると指定された図形に見える．図 1 は入力図形が二つの場合の例で，太線が視体積交差メッシュである．この例では，視体積交差メッシュは 2 次元メッシュではなく，1 次元メッシュ（ワイヤーフレーム）になっている．本研究では，入力図形が二つの視体積交差メッシュに限定して，その接続性を効率的に計算する手法を提案する．また，連結な視体積交差メッシュの錯視立体作成への応用についても述べる．
入力のサイズ（二つの図形の複雑度の和）を n で表すと，視体積交差メッシュの計算には O(n2 ) の時間複雑度と O(n2 ) の空間複雑度がかかる．そのため，視体積交差メッシュを陽に構築してから接続性を計算すると O(n2 ) 時間と O(n2 ) 空間が必要になる．提案手法は，計算位相幾何学の二つのツール• merge 木（サブレベルセットもしくはスーパーレベルセットの位相の変化を表したグラフ）• persistence pairingを利用して，視体積交差メッシュを陽に構築せずにその接続性を判定することに成功した．これにより時間複雑度，空間複雑度をともに O(n log n) まで下げることができた．
杉原によって提案された変身立体 (ambiguous cylinder) は錯視立体の一種で，「二つの特定の視点から観察すると，全く異なる形に見える」という境界曲線を持つ “円柱” である．変身立体の境界曲線は，円柱の側面に遮蔽されないように構築しなければならない．視体積交差メッシュの “最上部” は円柱の側面に遮蔽されずに見ることができる（図 2）．そのため，視体積交差メッシュが連結な場合は，それを変身立体の連結な境界曲線として利用することができる．
円柱側面の視線方向1D1
図1D2

押し出し方向視線方向2

図 2 入力図形（黒色の太線）と視体積交差メッシュ（濃い青色の領域）の断面図．視体積交差メッシュの二つの図形 D1 , D2 に対する視体積交差メッ“最上部” は円柱の側面（薄い青色の領域）に遮蔽さシュ（黒色の太線）．

れない．

1

粒子法のためのポリゴンと粒子の混合境界表現
室谷浩平（公益財団法人 鉄道総合技術研究所）
流体シミュレーションにおいて、流体と接する固体壁に境界条件を設定する必要がある。流体シミュレーションとして粒子法を用いた場合、流体と接する固体壁を表現するために、図１のような「固体壁を固体壁粒子の集まりとして扱う方法」と図２のような「固体壁を固体壁ポリゴンで扱う方法」が存在している。流体シミュレーションにおけ図１．固体壁を固体壁粒子

図２．固体壁を固体壁ポリる粒子法では、計算対象の粒子を中心とした影響半径内にの集まりとして扱う方法

ゴンで扱う方法

入る粒子の物理量を積分する必要がある。「固体壁を固体壁粒子のみで計算する方法」の場合は、固体壁付近の流体粒子は、影響半径内に入る固体壁内部の物理量を積分する必要があるため、影響半径内に入る固体壁粒子を積分点とみなして、固体壁粒子がもつ物理量の重み付加算を行う。
固体壁内部の物理量は流体部分の物理量から決まるため、固体壁粒子を配置して物理量を与える必要なく、流体部分の物理量から固体壁内部の積分ができる。この原理をもちいるのが、「固体壁を固体壁ポリゴンのみで計算する方法」

図３．固体壁粒子と固体壁ポリゴンの併用である。
「固体壁を固体壁ポリゴンのみで計算する方法」の場合、流体粒子の影響半径内に固体壁ポリゴンの面が唯一であれば、アルゴリズムは単純であり精度良く計算できる。これは、固体壁ポリゴンの面の十分に内部に限られる。一方
で、流体粒子の影響半径内に固体壁ポリゴンの頂点や辺が含まれるような場合、固体壁ポリゴン面が２つ以上存在するため、固体壁ポリゴンを計算するアルゴリズムが複雑になる。
本研究では、図３にしめすように、固体壁の大部分を占図４．車輪レール間の水膜の挙動解析

める固体壁ポリゴンの面の十分内部には、計算コストの低い「固体壁ポリゴン」を配置し、固体壁ポリゴンを用いた場合にアルゴリズムが複雑になる固体壁ポリゴンの辺や頂点の部分には、精度が良く、計算が単純である「固体壁粒子」を配置することで、計算コストが低く、アルゴリズムが単純で、精度が良い「固体壁に固体壁粒子と固体壁ポリゴンを併用する方法」を提案する。
図４と図５は、車輪とレール間の水膜の挙動解析の車輪とレールに固体壁粒子と固体壁ポリゴンを併用する方法で解析を実施した例である。

図５．固体壁粒子と固体壁ポリゴンの併用例

2

剰余類を用いた魔方陣の効率的な数え上げについて
山本 修身 (名城大学)

On Eﬃcient Enumeration of Magic Squares Using Residue ClassesOsami Yamamoto (Meijo University)

1

魔方陣と剰余魔方陣の定義および魔方陣の総数について

n 次魔方陣とは 0 から n2 − 1 までの整数を重複なく n × nのマトリックス状に並べたもので，縦，横および対角線上の数の和がすべて等しい（魔法和条件）もののことである．n 次魔方陣の集合を Mn と書く．Mn の任意の要素 m = [x1 , . . . , xn2 ]に対して魔 方陣を 構成す る数を 整数 p で割 った余 りに置 き

7910114196221211816213172032352401514128Fig. 1 An optimal assignment order of magic square oforder five derived by a simulated annealing algorithm. Thevalues of the variables in red squares are determined byfour variables already determined.

換えた並び [x1 mod p, . . . , xn2 mod p] を剰余魔方陣と呼び

ϕp (m) = m mod p と書くことにすれば，整数 p による n 次
剰余魔方陣の集合は RMnp = ϕp (Mn ) = {ϕp (m) | m ∈ Mn }と定義される．逆に r ∈ RMnp に Mn の部分集合 Xr = {m ∈Mn | ϕp (m) = r} を対応させれば ϕp は Mn 上の類別を与!
える．すなわち， r∈RMnp Xr = Mn となる．この性質から"p |Xr | が得られ，何らかの方法によって，そ|Mn | =r∈RMn
れぞれの |Xr | が求まれば n 次魔方陣の総数を求めることがでことにより約 60 分の 1 まで Xr の個数を減らすことができる．

本稿では P Mnp を用いた魔方陣の総数の計算法を提案する．

ぞれについてその要素をバックトラック法で求めると効率が悪

ただし，この割合は p に依存する．

RMnp のそれぞれの要素についてこのような変換で結ばれる要素を縮約してから，それぞれの Xr に含まれる魔方陣を計算する

きる．

ことができる．この場合，個別に得られた RMn の要素のそれ
p

特に数え上げ可能な魔方陣の集合のうち最大と思われる 5 次魔い．そこで，RMn の要素をメモリ上に木構造として展開し，そp方陣 M5 の要素数の計算法について説明する（6 次魔方陣は約の木に沿って Mn の要素を列挙していく方法をとる．

1.77 × 1019 個存在し [1]，数え上げ不可能と思われる）．5 次まで

さらに，ある程度大きな p について剰余魔方陣の集合を直接の魔方陣の総数は通常のバックトラック法を用いて数え上げる求めるのではなく，その約数 q による剰余魔方陣の集合 RMnq

ことができる．n = 5 については，総数が 22 億程度あり（普通pをあらかじめ求めて，その結果から RMn を求めることにより，習慣的に回転と裏返しによるパターンを同一視して数えるのでパターン数は 8 分の 1 となるが，ここでは同一視していない），普通に数えると 10 時間から 100 時間程度の計算時間を要する．
本稿では剰余魔方陣を用いてより効率的な数え上げを試みる．

より効率的に集合を計算することができる．

Fig. 1 に示す順に要素の値を決めるバックトラック法を用いて5 次魔方陣の総数を計算した．この順序は simulated annealingを用いて出来る限り早くそれぞれの魔法和条件が満たされる並びとして求めたものであるが，実際には順序によって性能にゆら

2 5 次魔方陣数え上げのための提案手法

ぎがあるので，複数の順序を生成して性能の良さそうなものを

本節では，まず剰余魔方陣を直接計算する方法について考える．剰余魔方陣の集合 RMnp の満たす性質は次のとおりである．

選択した．以下のように 2 種類の剰余魔方陣の集合を経て M5の個数を数えた：

1. RMnp の要素は k = 0, . . . , p − 1 の数によって構成され，そRM55 → RM510 → M5 .

れぞれの k が出現する回数は ⌊(n − k)/p⌋ となる．
2. それぞれの要素の各行，各列および対角線上の数の和の p計算には Apple MacPro (CPU: Intel 8-core Xeon E5-1620 v3

3.5 GHz, メモリ: 64 GB, コンパイラ: clang 7.3.0, コンパイによる剰余はすべて (n2 − 1)n/2 mod p に等しい．
p
この性質を満たす並びをすべて列挙した集合を RMn と書こう．
p
RMn はこの集合の部分集合となっている．この集合は Mn と同様にバックトラック法によって求めることができるが，小さなp については Mn に比べてずっと小さな集合となる．また，求められたそれぞれの要素 r を Mn の部分集合 Xr と同一視すれば，RMnp を求めることは，Mn の分割を計算していることになる．
ここで，2 つの異なる Xr が魔方陣上の変換によって結ばれることがある．魔方陣には魔方陣性を保存する回転や裏返しなど

ラオプション: -O3) を用いた．この計算では RM55 の計算に10.63 秒，RM55 からの対称性等の除去と重複度の記録に 30.02秒，RM55 から RM510 を作るのに 39.91 秒，RM510 から M5 を数え上げるのに 12 分 10 秒を要し，合計 13 分 40 秒で数え上げた．この計算はすべてシングルコア上で行い並列機能は一切使用していない．
文

献[1] Pinn, K. and Wieczerkowski, C.: Number of magic squares
from parallel tempering Monte Calro. Int. J. Mod. Phys. C 9,pp. 541-547 (1998)[2] 大森 清美: 魔方陣の世界．日本評論社 (2013)

を含むいつくかの変換が知られている [2]．この変換によって結ばれる Xr の個数は同一であり，独立にそれぞれの個数を求める必要はない．5 次魔方陣については，このような変換を考慮する

3࣮ࣾձͰੜ͡Δਤ‫ܗ‬഑ஔ໰୊ʹର͢ΔΞϧΰϦζϜઃ‫ܭ‬தԝେֶ ཧ޻ֶ෦ ৘ใ޻ֶՊɹࠓງ ৻࣏ (Shinji Imahori)ਤ‫ܗ‬഑ஔ໰୊ͱ͸ɼ༷ʑͳେ͖͞Λͨ͠ਤ‫ܗ‬Λ‫ʹ͍ޓ‬ॏͳΒͳ͍Α͏ʹ༰‫ʹث‬഑ஔ͢Δ໰୊ͷ૯শͰ͋Γɼਤ‫ܗ‬ͷ‫ܗ‬ঢ়΍഑ஔ੍໿ɼ໨తؔ਺౳ʹΑΓ༷ʑͳछྨͷ໰୊Λ‫ؚ‬ΜͰ͍Δɽେ෦෼ͷਤ‫ܗ‬഑ஔ໰୊͸ NP ‫׬‬શͰ͋ΔͨΊɼޮ཰తʹ࠷దͳ഑ஔΛಘΔ͜ͱ͸೉͍͠ͱ͞Ε͓ͯΓɼඪ४తͳਤ‫ܗ‬഑ஔ໰୊ʹର͢Δۙࣅղ๏΍ൃ‫ݟ‬తղ๏ɼϝλઓུͷ‫͕ڀݚ‬੝ΜʹߦΘΕ͖ͯͨɽҰํɼ੡଄‫ۀ‬΍ӡ༌‫ۀ‬Λத৺ͱͯ͠ɼ࣮ࣾձʹ‫ݱ‬ΕΔ༷ʑͳ՝୊͕ɼਤ‫ܗ‬഑ஔ໰୊ͷ‫هͰࣜܗ‬ड़Ͱ͖Δ͜ͱ͕஌ΒΕ͓ͯΓɼ࣮༻্͔Β΋ॏཁͳ໰୊Ͱ͋Δͱೝࣝ͞Ε͍ͯΔɽ͔͠͠ɼ࣮ࣾձͰੜ͡Δਤ‫ܗ‬഑ஔ໰୊͸ɼ‫ݸ‬ʑͷ໰୊ʹಛ༗ͷෳࡶͳ੍໿৚݅΍໨తؔ਺Λ༗͢Δ͜ͱ͕ଟ͘ɼඪ४తͳ໰୊ʹର͢ΔΞϧΰϦζϜΛͦͷ··ద༻͢Δ͜ͱ͕೉͍͠ͱ͍͏ঢ়‫͕گ‬ੜ͡Δɽຊ‫ݚ‬‫Ͱڀ‬͸ɼ͜ͷΑ͏ͳෳࡶͳਤ‫ܗ‬഑ஔ໰୊ʹର͢ΔΞϧΰϦζϜઃ‫ݕ͍ͯͭʹܭ‬౼Λߦ͏ɽຊ‫Ͱڀݚ‬ѻ͏໰୊͸࣍ͷ 2 ͭͰ͋Δɽ͜ΕΒͷ໰୊͸ɼӡ༌‫͓ۀ‬Αͼ੡଄‫ʹࡍ࣮Ͱۀ‬ੜͨ͡՝୊Λɼਤ‫ܗ‬഑ஔ໰୊ͱͯ͠ఆࣜԽͨ͠໰୊Ͱ͋Γɼ2015 ೥ͱ 2018 ೥ʹ։࠵͞Εͨʢ։࠵தͷʣਤ‫ܗ‬഑ஔΞϧΰϦζϜͷઃ‫ܭ‬ίϯςετʹ͓͍ͯ՝୊ͱͳͬͨ໰୊Ͱ͋ΔɽॳΊͷ໰୊͸ɼ௚ํମͷ‫ܗ‬ঢ়Λ΋ͭෳ਺ͷίϯςφͱՙ෺͕༩͑ΒΕͨͱ͖ʹɼશͯͷՙ෺Λίϯςφ಺ʹ഑ஔ͠ɼ࢖༻͢Δίϯςφͷ਺ͷ࠷খԽΛ໨తͱ͢ΔɼίϯςφϩʔσΟϯάͱ‫ݺ‬͹ΕΔ໰୊Ͱ͋Δɽඪ४తͳ 3 ࣍‫ݩ‬ͷ௚ํମ഑ஔ໰୊ʹର͢ΔΞϧΰϦζϜ͕ଘࡏ͢Δ͕ɼ͜͜Ͱ͸ࣗಈं෦඼Λ഑ૹ͢Δ͜ͱΛ૝ఆͨ͠ɼ༷ʑͳ੍໿৚݅Λߟྀ͢Δඞཁ͕͋Γɼඪ४ΞϧΰϦζϜΛͦͷ··ద༻࣮ͯ͠༻తͳՙ෺ͷ഑ஔΛಘΔ͜ͱ͸೉͍͠ɽຊ‫Ͱڀݚ‬͸ɼඪ४తͳਤ‫ܗ‬഑ஔ໰୊Ͱ͋Δɼ
ʢ1 ࣍‫ݩ‬ʣφοϓαοΫ໰୊ͱ 2 ࣍‫ݩ‬ϏϯύοΩϯά໰୊ʹର͢ΔΞϧΰϦζϜΛ‫͢༻׆‬Δ͜ͱʹΑΓɼෳࡶͳ੍໿৚݅Λ༗͢Δ 3 ࣍‫ݩ‬௚ํମ഑ஔ໰୊Λղ͘͜ͱΛࢼΈͨɽఏҊͨ͠ΞϧΰϦζϜɼ͓ΑͼϕϯνϚʔΫ໰୊ʹର͢Δ਺஋࣮‫ݧ‬ͷ݁ՌΛใࠂ͢Δɽ
2 ͭ໨ͷ໰୊͸ɼ௕ํ‫ܗ‬ͷ‫ܗ‬ঢ়Λ΋ͭෳ਺ͷ฼ࡐͱ੡඼͕༩͑ΒΕͨͱ͖ʹɼશͯͷ੡඼Λ฼ࡐ಺ʹ഑ஔ͠ɼ࢖༻͢Δ฼ࡐͷ਺ͷ࠷খԽΛ໨తͱ͢Δɼ2 ࣍‫ݩ‬ϏϯύοΩϯά໰୊ͱ‫ݺ‬͹ΕΔ໰୊Ͱ͋Δɽ͜͜Ͱ͸ɼΨϥε࢈‫Ͱۀ‬ੜ͡Δ 2 ࣍‫ݩ‬ϏϯύοΩϯά໰୊Λߟ͑Δ͕ɼඪ४తͳ੍໿৚݅ʹՃ͑ͯɼ࣍ͷ 3 ͭͷಛ௃తͳ৚݅Λߟྀ͢Δඞཁ͕͋Δɽ1. ੡඼Λ฼ࡐ͔ΒΪϩνϯΧοτʹΑͬͯ੾Γग़͢ඞཁ͕͋Δɼ 2. ฼ࡐʹ͸ই͕͍͍ͭͯΔՕॴ͕͋Γɼ͜ͷ෦෼͸੡඼ͱͯ͠ར
༻͢Δ͜ͱ͕Ͱ͖ͳ͍ɼ3. ੡඼ʹ͸෦෼తͳ੡଄ॱং͕༩͑ΒΕ͓ͯΓɼ͜ͷॱংʹैͬͯ੡඼Λ഑ஔ͢Δඞཁ͕͋Δɽ͜ͷ໰୊͸ɼ‫ࢪ࣮ࡏݱ‬தͷਤ‫ܗ‬഑ஔΞϧΰϦζϜઃ‫ܭ‬ίϯςετͷ՝୊Ͱ͋Γɼ‫ࡏݱ‬ΞϧΰϦζϜΛઃ‫͍ͯ͠ܭ‬Δɽ‫্్ڀݚ‬ͷ಺༰ʹ͸ͳΔ͕ɼ͜ͷ໰୊ʹର͢ΔऔΓ૊Έʹ͍ͭͯ΋঺հ͢Δɽ

4

産業応用に向けた形状処理技術
東京大学大学院工学系研究科精密工学専攻 長井 超慧E-mail: yukie@den.t.u-tokyo.ac.jp

概要：製品製造過程の検査・計測・形状取得等において、製品現物の 3 次元スキャンは欠かせない技術である。3 次元スキャンには、現物の表面形状のみ取得する光学式スキャンと、現物の内部形状も取得可
能な X 線 CT スキャンがあり、スキャンデータの用途や現物の性質により使い分けられている（図１）。
産業応用における形状スキャンの特徴の一つは、計測対象となる製品のサイズ・形状特徴・素材が多様なことである。これらの多様性により、品質の良いスキャンデータの取得やデータ処理が困難になっている（図２左）。現在、スキャン装置の高性能化・カスタマイズ化が進んでいるが、ユーザは従来人の手で達成されてきた高い形状精度に迫る精度を求めており、その期待に応える品質のスキャンデータを得ることは未だ難しい。形状処理技術は、現時点でのハードウェア技術だけでは解決できないスキャンデータの高品質化に有効であると期待される技術である。また、スキャンデータからの形状抽出、形状解析等にもソフトウェアによる形状処理技術は欠かかすことができない。
本発表では、
産業応用において 3 次元スキャンの利用を促進するための形状処理技術の利用例として、光学式スキャンデータに対するノイズ・欠損に頑健な表面メッシュ生成法、X 線 CT スキャンデータから効率よく組立品の部品毎の表面メッシュを抽出する手法（図２右）、X 線 CT データから検査・解析用データを生成する手法等を紹介する。

図１ 産業応用においてスキャンデータの計算機処理が果たす役割

図２ アーチファクト（放射状の黒線）を含む CT データと、ソフトウェアによるセグメンテーション

5Spherical Laguerre Voronoi Diagram as a Tool for
Modeling the Spherical Tessellations
Supanut Chaideea , Kokichi Sugiharabba
Department of Mathematics, Faculty of Science, Chiang Mai University, Thailand
Meiji Institute for Advanced Study of Mathematical Sciences, Meiji University, Japan

Abstract
Many natural phenomena display as tessellation patterns. We focused on thetessellation patterns of the objects which can be approximated by spheres. In computational geometry, Voronoi diagrams, the partitioning of space in a way that eachpoint in the space is assigned to the nearest point called generator, are fruitfulconcepts to analyze tessellation patterns.
We were interested in the spherical Laguerre Voronoi diagram (SLVD), one of
the weighted Voronoi diagrams on the sphere. We focused on the viewpoint of
the inverse Voronoi diagram problem. In the recognition problem, the problem
to judge whether or not the given tessellation is a Voronoi diagram, we studied
the transformation of polyhedra corresponding to the given SLVD and proposed
the algorithm to judge whether the given tessellation is SLVD or not. With theproperties of those polyhedra, we were able to propose algorithms for approximating
given spherical tessellations with the SLVD. The experiments were done using theplanar photographic images of the fruit skin patterns. We found that it is promising
to use the SLVD as a tool for modeling the tessellation in the real world, especiallyin the case of fruit skins.
In addition to the inverse Voronoi diagram problem, we studied the model togenerate the tessellation patterns on the sphere dynamically. By assumptions inreal-world, we proposed the generator pushing model and simulated with artificiallygenerated data. The results showed the tendency of the distribution of resulting
spherical circles. Therefore, it is promising to investigate the proposed processes
and define it as the centroidal spherical Laguerre Voronoi diagram.

aThe talk of the first author is a part of the follow-up research fellowship program (FY2018), arranged
by Japan Student Services Organization (JASSO), Japan.
aE-mail address: supanut.c@cmu.ac.th (S. Chaidee).

6

幾何処理で正確であってほしい情報と近似算法
今井 敏行 11 和歌山大学システム工学部

e-mail : timai@sys.wakayama-u.ac.jp

1

正確であってほしい構造情報ている.

計算機で保持される幾何情報は, 面や辺の数,それらの隣接・接続情報といった構造にかかわる情報 (構造情報) と辺の長さや角の大きさといった寸法にかかわる情報 (計量情報) に分かれる. 大雑把に言って, 幾何情報のうち離散値を持つのが構造情報, 連続値を持つのが計量情報である [1]. どちらが先かといえば, 構造情報である. 例えば, 辺なら, それあることが分かって初めてその長さが意味を持つからである. 効率的な算法は, しなくてもよい計算を省くことで達成される. しなければならない計算は省けないからである. 一般的に, 近似をしたら近似解しか得られないという常識がある. しかし構造情報は離散値をとる. したがって, 近似算法
でも構造情報なら厳密解が得られる可能性がある. 厳密な構造情報が得られてから, 計量情報は必要な精度で計算すればよい.
本研究においては幾何処理の分野で近似算法により厳密解を求める処理の枠組みを作りを目指している. ここでは, 生成元が線分や円の勢力圏図構成を点列で近似した勢力圏図構成算法
で厳密解を求める方法を例にその枠組みを示す.
円や線分を一様に細かく点列で近似すると,計算量の増大が問題となる.

2

本研究の枠組みとしての基本算法
構成算法の基本的な形は, 次のとおりである.
0. 初期近似をする
1. 構造情報が全域で正しければ終了.
正しいと言い切れない部分があれば 2 へ.
2. その部分だけ近似精度を上げ 1 に戻る.

初期近似においては, 線分や円を数点で近似する. 構造情報の正しさは, 現在得られている領域の境界辺が, すべて局所的に存在するといえるか判定して調べる. 存在するといえないときに, 判定に影響するところに点を付加する. 局
所的に存在すると全域でいえれば構造情報は正しい. 図 1 に対して, 図 2 の点数で正しい構造情報が得られる.

図 2. 構造的に正しい勢力圏図

円と線分の勢力圏分割も基本的に同様に得られる (図 3, 無限に伸びる辺を省略).

図 1. 一様近似による勢力圏図

例えば図 1 くらいの点の数でも中央部分で領域の隣接関係が正しくない. 構造情報を厳密に求めるだけなら多くの部分で粗い近似をする.
詳細な近似が必要なのは, 図形のごく一部の, 構造情報の決定が困難な場合に限られる. 詳細な近似が必要な部分が少ないため高速性も確保されると期待できる. これが本研究の特色となっ図 3. 円と線分の勢力圏

本研究の一部は科学研究費補助金による.
参考文献[1] 杉原厚吉, 計算幾何学, 朝倉書店, 2013.

7࣮൙Ոѕӌʱ๑ɣɾౙୈ‫́˚˕˟ث‬ƪˁ˴˙˽ʊՂʄɮ
ਂ୎ζʊહ෾ɶɾε࣭٫ઢʍߒʞ੿‫ۇ‬ຒ६Ƹज‫ڗ‬੝ӌ੝ӌϙˉˋ˘˲࣮൙ӌٰ֖Ѡ, JST ɴɬɫɰƹࢬࢼौѢƸज‫ڗ‬੝ӌ੝ӌϙˉˋ˘˲࣮൙ӌٰ֖Ѡƹ੝ন‫܌‬૰Ƹज‫ڗ‬੝ӌ੝ӌϙˉˋ˘˲࣮൙ӌٰ֖Ѡ, JST CRESTƹ‫ׯ‬௻ƒ࣮൙૾ऊիࡱʱ๑ɣɾఌ‫ז‬ʍ‫ۄ‬ຆѓʱ෾଺ʇɸʪƒˋ˰ƪ˚ʴ˂˼ʇ‫ڐ‬ʏʫʪٰ֖ɫॳʲʊʉʂʅɣʪƓචٰ֖ʆʎƒறʊƒൢඖ֝ʍԛ๽ʊહ෾ɸʪƓ֝ʎ˅˱˷˝˘ʵʱ‫ح‬२ɸʪʉʈƒࠔ҇଺ʉஞഐʇɶʅઢʨʫʅɣʪɫƒ࣮൙૾ऊիࡱʱ๑ɣʅ˅˱˷˝˘ʵʣɼʍഷѓʱ٫ઢɶƒɼʫʱԛ๽ʊ๑ɣʪٰ֖ʎƒʚʇʲʈ‫ۼ‬ʮʫʅɣʉɣƓɼɲʆƒචٰ֖ʆʎƒ֝ʍʡʃࠔ҇१ʱж๑ɶɾԛ๽ˉˋ˘˲ʍҟౙʱ෾ೀʇɶƒൢඖ֝ʍ‫ۼ‬ஞʱGPS ʱ๑ɣʅ՝໻ɶƒɼʫʱ҈উɸʪɲʇʆƒ֝ʍ˅˱˷˝˘ʵ҈উʣƒ˅˱˷˝˘ʵʊ‫ڇ‬ʫʪε࣭٫ઢࠬ൥ʍ‫ۥ‬યʱ෾޼ɸƓࣣ՝ʍʧɥʉ෾଺ʱత‫ض‬ʊƒචౙ೅ʆʎƒࢬ՜෱ʍߢԨౙୈ‫́˚˕˟ث‬ƪˁʊ੆ɸʪॐ๽˴˙˽ [1] ʊՂʄɮƒ˟˕˚́ƪˁ˴˙˽ʍਂ୎ζʱ๸๑ɶɾε࣭٫ઢࠬ൥ʊʃɣʅࡲʘʪƓ࣮൙Ոѕӌʎƒ஍‫˽˙˴ك‬ɫ߭োʊଜʠʪਵํ੄ʉʈʊԪɸʪՈѕӌʆɡʩƒ஍‫˽˙˴ك‬ʎ Riemann ਵํ੄ʇʞʉɺʪɲʇɫઢʨʫʅɣʪƓ࣮൙Ոѕӌʱ๑ɣɾౙୈ‫ث‬˟˕˚́ƪˁ˴˙˽ʎƒ˟˕˚́ƪˁʊ੆ɸʪ஍‫˽˙˴ك‬ɫଜʠʪ Riemann ਵํ੄ࣣʍߢ‫ػ‬໑˴˙˽ʆɡʪƓɲʍʧɥʉ˴˙˽ʱ۵ɧʪɲʇʆƒ௰ίʍॿ଺˟˕˚́ƪˁ˴˙˽ʊ੆ɶʅƒɼʫʱՂ৛ʇɶɾߢԨౙୈ‫˽˙˴ث‬ʱ‫ۥ‬યɸʪɲʇɫʆɬƒɴʨʊƒɼʫʱํƧʉߢ‫ػ‬໑҈উࠬ൥ʇٗʒʃɰʪɲʇɫʆɬʪƓ˟˕˚́ƪˁʊ੆ɸʪ஍‫˽˙˴ك‬ʇɶʅʎƒ޼ॐ˻̅˒˲˂˻˧˴˙˽ɫઢʨʫʅɣʪƸ[2] ʉʈƹɫƒ޼ॐ˻̅˒˲˂˻˧˴˙˽ʎƒˣ˻˳ƪˑʍડʊʧʂʅƒ੖ѓʇʡ‫ڐ‬ʏʫʪਂ୎ζʱ՟ɲɸɲʇɫɡʪƓɼɲʆƒචٰ֖ʆʎƒɲʫʱ๸๑ɶƒਂ୎ζʍอ෗ʊʧʂʅ˟˕˚́ƪˁʍࠃ଺ഷѓʱ٫ࡰɸʪࠬ൥ʱ‫ۥ‬યɶƒࠄ‫ݣ‬ʊൢඖ֝ʍ˅˱˷˝˘ʵε࣭٫ࡰʊж๑ɸʪƓ‫ޖ‬۵ഞ‫ٯ‬[1] T. Yaguchi and M. Komatsu, Autoregressive Models on Statistical RiemannianManifolds for Analysis of Evolutionary Networks, Data Science, Statistics & Visualisation 2018, book of abstracts, p. 118.
[2] G. Robins, P. Pattison, Y. Kalish and D. Lusher, An Introduction to Exponential
Random Graph Models for Social Networks, Social Networks. 29 (2007) 173–191.

8⬻ࡢ┤ゅඃඛᛶࢆ฼⏝ࡋࡓከ⩏❧యࡢタィἲ      ᮡཎཌྜྷ㸦᫂἞኱Ꮫࠊඛ➃ᩘ⌮⛉Ꮫ࢖ࣥࢫࢸ࢕ࢸ࣮ࣗࢺ㸧 」ᩘࡢゎ㔘ࡀ࡛ࡁࡿ 2 ḟඖࡢከ⩏ᅗᙧࡣࠊࢿࢵ࣮࢝ࡢ❧᪉యࠊࢩ࣮ࣗࣞࢲ࣮ࡢ㝵ẁ࡞࡝ྂࡃ࠿ࡽ▱ࡽࢀ࡚࠸ࡿࡀࠊ3 ḟඖ❧య࡛ࡶྠᵝ࡟ከ⩏ⓗ࡞ゎ㔘ࡀ࡛ࡁࡿࡶࡢࡀぢࡘ࠿ࡗ࡚࠸ࡿࠋぢࡿ᪉ྥ࡟ࡼࡗ࡚␗࡞ࡿࢩ࢚ࣝࢵࢺࡀぢ࠼࡚ࡃࡿከࢩ࢚ࣝࢵࢺ᙮้ࠊ❧యࡢྠࡌ㒊ศࢆぢ࡚࠸ࡿࡢ࡟ぢࡿ᪉ྥ࡟ࡼࡗ࡚␗࡞ࡿࡶࡢࡀぢ࠼࡚ࡃࡿከ⩏ᰕయ࡞࡝࡛࠶ࡿࠋࡋ࠿ࡋࠊࡑࡢ࡯࡜ࢇ࡝ࡣࠊ
2 ✀㢮ࡢゎ㔘ࢆᣢࡘࡶࡢ࡛࠶ࡿࠋ3 ✀㢮௨ୖࡢゎ㔘ࢆᣢࡘࡶࡢࡶ࠶ࡿࡀࠊࡑࡢసࡾ᪉ࡣⓎぢⓗ࡞᪉ἲ࡟㢗ࡽࡊࡿࢆᚓ࡞࠸ࡶࡢ࡛࠶ࡗࡓࠋࡇࢀ࡟ᑐࡋ࡚ࠊᮏ◊✲࡛ࡣࠊ2 ✀㢮ࡢከ⩏ᛶࠊ3 ✀㢮ࡢከ⩏ᛶࠊࡉࡽ࡟ࡑࢀࢆ⤌ࡳྜࢃࡏࡓ 6 ✀㢮ࡢከ⩏ᛶࢆࡶࡘ❧యࡢ⤫୍ⓗ࡞タィἲࢆᥦ᱌ࡍࡿࠋ
 2 ḟඖᅗᙧࡣዟ⾜ࡁࡢ᝟ሗࢆᣢࡓ࡞࠸ࡓࡵࠊ❧య࡜ࡋ࡚ࡢゎ㔘ࡣ↓㝈ࡢྍ⬟ᛶࡀ࠶ࡿࡀࠊ⬻ࡣࡑࡢ୰࡛᭱ࡶ┤ゅࢆከࡃྵࡴ❧యࢆ▱ぬࡍࡿഴྥࡀ࠶ࡿࠋࡲࡓࠊୗ࠿ࡽぢୖࡆࡓ≧ἣࡼࡾୖ࠿ࡽぢୗࢁࡋࡓ≧ἣࢆ▱ぬࡍࡿഴྥࡀᙉ࠸ࠋࡇࢀࡽࡢᚰ⌮Ꮫⓗ▱ぢࢆḟࡢࡼ࠺࡟฼⏝ࡍࡿࠋ㠃ࡀ஫࠸࡟┤ゅ࡟᥋⥆ࡉࢀ࡚࡛ࡁࡓከ㠃యࢆ┤ゅ❧య࡜࿧ࡪࠋ┤ゅ❧యࡢᖹ⾜ᢞᙳᅗࡣ 3 ⤌ࡢᖹ⾜⥺ࡢࡳ࡟ࡼࡗ࡚ᥥ࠿ࢀࡓᅗ࡜࡞ࡿࠋࡇࡢᅗࢆỈᖹ㠃ୖ࡟⨨ࡁࠊ୍⤌ࡢᖹ⾜⥺ࡀᆶ┤࡟ぢ࠼ࡿ᪉ྥ࠿ࡽᩳࡵ࡟ぢୗࢁࡍ࡜ࠊ⬻ࡣ┤ゅ❧యࢆୖ࠿ࡽぢୗࢁࡋࡓ࡜࠸࠺ゎ㔘ࢆࡍࡿ࡜ᮇᚅ࡛
ࡁࡿࠋࡉࡽ࡟▱ぬࡉࢀࡿ❧యࡣࠊᅗࢆṇ㠃࠿ࡽぢࡓ᫬࡜ẚ࡭ࡿ࡜ᆶ┤᪉ྥ࡟ᅽ⦰ࡉࢀࡓᙧ࡜࡞
ࡿࠋࡋࡓࡀࡗ࡚ࠊ3 ⤌ࡢᖹ⾜⥺ࡢࡑࢀࡒࢀࡀᆶ┤࡟ྥࡃ᪉ྥ࠿ࡽぢࡓ᫬ࠊูࡢ᪉ྥ࡬ᅽ⦰ࡉࢀ
ࡓ❧య࡜࡞ࡿࡓࡵࠊ஫࠸࡟␗࡞ࡿ❧య࡛࠶ࡿ࡜࠸࠺༳㇟ࡀ⏕ࡲࢀࡿࠋࡉࡽ࡟ࠊ୍⤌ࡢᖹ⾜⥺ࡀᆶ┤࡟ぢ࠼ࡿ᪉ྥࡣ஧ࡘ࠶ࡿࡀࠊୖ࠿ࡽぢୗࢁࡍ࡜࠸࠺ゎ㔘ࡀඃඛࡉࢀࡿࡓࡵ࡟ࠊ஫࠸࡟㧗ࡉࡀ཯㌿ࡋࡓ❧యࡀ▱ぬࡉࢀࡿࠋࡇࡢᢞᙳᅗ࡟ࠊ㔜ຊ᪉ྥࢆ⾲ࡍ 3 ḟඖᵓ㐀ࢆ㏣ຍࡍࡿ࡜ࠊୖࡢ
▱ぬࡀࡉࡽ࡟ᙉࡃ࡞ࡿࠋ௨ୖࡢࡇ࡜ࢆ฼⏝ࡍࡿ࡜ࠊ㸦㸯㸧஫࠸࡟཯ᑐ᪉ྥ࠿ࡽぢୗࢁࡍ࡜㧗ࡉࡀ཯㌿ࡋ࡚␗࡞ࡿ❧య࡟ぢ࠼ࡿከ⩏ᛶ࡜ࠊ
㸦㸰㸧3 ⤌ࡢᖹ⾜⥺ࡢࡑࢀࡒࢀࡀᆶ┤࡟ぢ࠼ࡿ᪉ྥ࠿ࡽぢࡓ࡜ࡁ␗࡞ࡿ❧యࡀ▱ぬࡉࢀࡿ࡜࠸࠺ከ⩏ᛶࡀ⏕ࡲࢀࡿࠋᅗ㸯ࡣࠊ㝵ẁᅗᙧ࡟ 3 ḟඖᨭᰕࢆ㏣ຍࡋࡓ❧య࡟ࡼࡿ㧗ࡉ཯㌿ࡢከ⩏ᛶࠊᅗ 2 ࡣ┤ゅ❧యࡢᢞᙳᅗ࡟᪝ࢆ㏣ຍࡋࡓ❧య࡟ࡼࡿ 3✀㢮ࡢከ⩏ᛶࢆᐇ⌧ࡋࡓ౛࡛࠶ࡿࠋ

ᅗ 1㸬㧗ࡉ཯㌿❧యࠕ㝵ẁࡢ❧య஺ᕪࠖ   ᅗ 2㸬3 ᪉ྥከ⩏❧యࠕ᪝ࡢ࠶ࡿ㢼ᬒࠖ9

MIMS 現象数理学研究拠点共同研究集会
幾何的解析と形状表現の数理アブストラクト集
２０１８年８月２４日（金）・２５日（土）明治大学 中野キャンパス６階 研究セミナー室３（６０３号室）
主催：明治大学先端数理科学インスティテュート（MIMS）
連絡先：杉原厚吉（MIMS）

kokichis@meiji.ac.jp

森口昌樹（実行委員会事務局），MIMSmoriguchi@meiji.ac.jp