Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
On Space Filling Curves: Its Beauty and Applica...
Search
cannorin
July 25, 2019
Science
0
290
On Space Filling Curves: Its Beauty and Applications
cannorin
July 25, 2019
Tweet
Share
More Decks by cannorin
See All by cannorin
AltJS を作るなら型変換を入れた方がいい
cannorin
0
1.3k
A Journey to Type-safe Vectors in F#
cannorin
6
11k
Audio Experience is greatly improved in VR: A Worked Example
cannorin
0
1.6k
TidalCycles - Haskell meets Music
cannorin
0
1.5k
Making Indian Curries - at Home!
cannorin
2
1.5k
A brief introduction to type inference
cannorin
4
2.4k
Other Decks in Science
See All in Science
アナログ計算機『計算尺』を愛でる Midosuji Tech #4/Analog Computing Device Slide Rule now and then
quiver
1
250
Machine Learning for Materials (Challenge)
aronwalsh
0
320
ttl2html (RDF/Turtle to HTML)
masao
0
110
白金鉱業Meetup Vol.16_数理最適化案件のはじめかた・すすめかた
brainpadpr
4
1.9k
凸最適化からDC最適化まで
santana_hammer
1
290
機械学習 - pandas入門
trycycle
PRO
0
310
04_石井クンツ昌子_お茶の水女子大学理事_副学長_D_I社会実現へ向けて.pdf
sip3ristex
0
610
2025-06-11-ai_belgium
sofievl
1
150
テンソル分解による糖尿病の組織特異的遺伝子発現の統合解析を用いた関連疾患の予測
tagtag
2
230
動的トリートメント・レジームを推定するDynTxRegimeパッケージ
saltcooky12
0
180
機械学習 - 決定木からはじめる機械学習
trycycle
PRO
0
1k
SciPyDataJapan 2025
schwalbe10
0
260
Featured
See All Featured
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
23
1.4k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
507
140k
The Art of Programming - Codeland 2020
erikaheidi
55
13k
The World Runs on Bad Software
bkeepers
PRO
70
11k
A designer walks into a library…
pauljervisheath
207
24k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
31
2.5k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
234
17k
Building Applications with DynamoDB
mza
96
6.6k
Building Better People: How to give real-time feedback that sticks.
wjessup
368
19k
Java REST API Framework Comparison - PWX 2021
mraible
33
8.8k
What’s in a name? Adding method to the madness
productmarketing
PRO
23
3.6k
KATA
mclloyd
32
14k
Transcript
VRCLT #3 空間充填曲線,その魅力と意義 cannorin
だれ • Twitter: @cannorin_vrc • Study: 数理論理学 プログラム言語の理論 • Job:
F# プログラマ • in VRC: VOLT Enthusiast VRCLT Speaker (#2~)
空間充填曲線とは ペアノ曲線 (0) ヒルベルト曲線 (1)
空間充填曲線とは(再帰的に細かくしていく) ペアノ曲線 (1) ヒルベルト曲線 (2)
空間充填曲線とは(再帰的に細かくしていく) ペアノ曲線 (2) ヒルベルト曲線 (3)
空間充填曲線とは(再帰的に細かくしていく) ペアノ曲線 (3) ヒルベルト曲線 (4)
空間充填曲線とは → 空間を充填する曲線(それはそう) ペアノ曲線 (∞) ヒルベルト曲線 (∞)
空間充填曲線とは / 一般化 n 次元への一般化もできる(これは 3D ヒルベルト曲線)
空間充填曲線とは / 定義 n 次元の単位(超)立方体を “埋め尽くす”(一次元の)曲線 ↓ 形式的には (一次元の)単位区間 [0,
1] から n 次元の単位(超)立方体 [0, 1]ⁿ への連続写像
なぜ埋め尽くせるのか? ゲオルク・カントール (1845 - 1918) 実数 ℝ の濃度と n- 次元ユークリッド空間
ℝ ⁿ の 濃度は等しい + ( non-degenerate な)区間 (単位区間 [0, 1] など)も等しい
なぜ埋め尽くせるのか? / 濃度とは? 全単射が存在(=1対1対応を作れる)⇔ 濃度が等しい 「濃度」=「要素の個数」概念の一般化(無限もOK) |X| = |Y| (
ちなみに |ℝ| > |ℕ| )
なぜ埋め尽くせるのか? ゲオルク・カントール (1845 - 1918) | [0, 1] | =
|ℝ| = |ℝⁿ| [0, 1] ℝ と と ℝ ⁿ の間の全単射の存在を証明
なぜ埋め尽くせるのか? ジュゼッペ・ペアノ (1858 - 1932) 全単射が存在するなら, 連続にできるのだろうか? || 空間を一本の曲線で 埋め尽くせるのだろうか?
なぜ埋め尽くせるのか? ジュゼッペ・ペアノ (1858 - 1932) → 全単射にはならなかったが,埋め尽くせた! (ペアノ曲線)
なぜ全単射にならない? ℝ と ℝ ² は同相ではない ↓ 一点を取り除く 分離する→ ←
分離しない
なぜ全単射にならない? 一点を取り除いても分離しない ⇔ 自己交叉がある ⇔ 同じ点を何度も通る場所がある ⇔ 単射ではない! ※ 詳しくは解析学や位相空間論の知識が必要.
A.P.M Kupers, On Space-Filling Curves and the Hahn-Mazurkiewicz Theorem とか参照 ↑ 実は自己交叉してる
おもしろい応用例が色々ある • Google Maps のキャッシュの最適化 • 巡回セールスマン問題の高速なヒューリスティック手法 • 小型で高性能なアンテナの設計 •
大規模並列計算のロードバランシング • 衝突判定やレイトレーシングの高速化 • etc...
応用 / Bounding Volume Hierarchy 物体同士の衝突判定や,物体とレイの交差判定を効率化する ために,近くにある物体同士をグループ化して扱いたい 二分木にする → 判定回数を減らせる:
O(n) → O(log n)
応用 / Bounding Volume Hierarchy / 二分木構築の高速化 近くにある物体同士を検出して二分木を作るのが大変 → 空間充填曲線を使って走査する
空間充填曲線は右から左へと 走査するのに比べて, 平面上で近くにあるものが 直線上でも近くになりやすい → 順番に辿ればOK!
応用 / 空間充填曲線の locality 「平面上で近くにあるものが直線上でも近くになりやすい」 性質 (locality) が様々な分野に応用しやすい 実装が楽なのでヒルベルト曲線がよく使われるが, 使う曲線によって効率化の度合いが変わることもある
ところで・・・ 今回のスライドで使われている空間充填曲線の画像は, 私が所属している「株式会社ぺあのしすてむ」で 業務の一環として開発しているスマホアプリ 「 Peano Curves 」で作成されています ・現在オープンベータテスト中 ・アプリ名
: Peano Curves ・対応 OS: iOS/Android ・公式 Twitter: @PeanoCurves
Thank you for listening!