December 2016
Intermediate to advanced
440 pages
9h 44m
Japanese
Content preview from アルゴリズムクイックリファレンス 第2版
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
■
319
10
章
空間木構造
本章のアルゴリズムは、主にデカルト平面での強力な探索を行うために
2
次元構
造をどうモデル化したら良いかということについて扱う。これらのアルゴリズムは
5
章で取り上げた集合の要素を探す単純なものよりさらに強力なものとなっている。
次のようなアルゴリズムが含まれる。
最近傍
2
次元点集合
P
が与えられたとき、ターゲットクエリ点
x
に最も近い点を
決定する。これは、力任せ解の
O(n)
ではなく、
O(log n)
で解決できる。
範囲クエリ
2
次元点集合
P
が与えられたとき、与えた四角形の範囲にあるすべての
点を決定する。これは、力任せ解の
O(n)
ではなく、
O(n
0.5
＋
r)
で解ける。
ここで、
r
は、結果として返される点の個数である。
交差クエリ
2
次元長方形の集合
R
が与えられたとき、どの長方形がターゲット長方
形領域と交差するかを決定する。これは、力任せ解の
O(n)
ではなく、
O(log n)
で解ける。
衝突検出
2
次元点集合
P
が与えられたとき、これらの点を中心とする辺
s
の正方形
の間での交差を決定する。これは、力任せ解の
O(n
2
)
ではなく、
O(n log
n)
で解決できる。
構造とアルゴリズムとは、自然に高次元に拡張できるが、本章で扱う範囲は、便
宜上ごく普通の
2
次元構造にとどめる。本章の題名は、研究者が二分探索木の中心
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.