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.
304
■
9
章 計算幾何学
ころだというものである（
Palazzi and Snoeyink, 1994
）。
9.6
ボロノイ図
1986
年にフォーチュン（
Fortune
）は、
線分走査法
を、別の計算幾何学問題である、
デカルト平面の点集合
P
のボロノイ図（
Voronoi diagram
）作成に応用した。ボロノ
イ図は、生命科学から経済学まで広範囲で役立つ（
Aurenhammer, 1991
）。
ボロノイ図は、
n
個の
2
次元点集合
P
への各領域の距離に基づいて平面を領域に
分割する。
n
個の各領域は、他の点
p
j
∈
P
よりも点
p
i
∈
P
に近い点からなる。図9-8
は、（四角で示す）
13
点に対して計算したボロノイ図（黒い線）を示す。ボロノイ図は、
（図中の線の）ボロノイ辺で区切られた
13
の凸領域と（それらの交点の）ボロノイ点
からなる。ある点集合に対するボロノイ図を使って次のようなことができる。
●
凸包の計算
●
点集合内で最大空円を求める
●
各点の最近傍を見つける
●
集合内で最近点対を見つける
図9-8 ボロノイ図の例
9.6
ボロノイ図
■
305
フォーチュン走査法
（
Fortune Sweep
）は、線分交差を見つけるのに使われた
線分
走査法
に似たものを実装する。
線分走査法
では、既存の点を優先度付きキューに挿
入して、それらの点を ...
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.