線分交差判定計算幾何学とは線分交差判定線分交差列挙問題同一要素判定問題の帰着線分交差判定問題線分交差判定問題凸包構成凸包構成問題凸包の難しさ行進法グラハムスキャン法ソートとの関連分割法分割法の計算時間・点集合を分割してそれぞれの凸法を再帰的に求めるところは分割法と同じだが、分割する際に、適当な２つの点集合に分割する（ソートしない）２．PをP0とP1、ほぼ同じ大きさの２つに分割３．P0、P1のについて再帰呼び出しし、P0とP1の凸法を求める４．P1とP0の凸法の接線を求め、全体の凸法を作る・ソートが必要なくなったが、接線を２つ以上見つけなければならない・接線は２分探索で１つ求められるが、最悪接線はn本になるざっくりいって、O(nlogn)の時間が必要・工夫すると線形時間でできる１．P0の凸包とP1の凸包、両者に含まれる点oを見つける２．そのような点がなければ、接線は２つしかない。それを求める３．oから見て時計回り順にP0、P1の点を見て、凸包を作る（グラハムスキャンと同じ）・1つの点は2回しかアクセスされず、線形時間となる全体でO(nlogn)時間クイックハル・３次元以上の高次の次元で、凸包アルゴリズムはどうなるか？・まず、接線が接平面になる２つの凸包の接平面は、２つとは限らない・グラハムスキャンや行進法で使う「時計回り」という概念がない・点を逐次追加し、その点を含む接平面を追加する・３次元なら、２つの凸包の接平面をくるむように求められるので、分割法は動くボロノイ図ボロノイ図ボロノイ図の作り方1点追加すると垂直二等分線が交わると計算量の解析分割統治法分割統治法分割統治法計算量の解析・３次元以上の高次の次元で、凸包アルゴリズムはどうなるか？・ボロノイ領域は凸多面体になる・やはり「時計回り」という概念がない・点を逐次追加し、その点を含む領域を構成するには、凸多面体領域の面を求める問題になるまとめ