三角形分割

定義

入力空間を三角形（高次元では単体）の網目に分割すること。メッシュの頂点でのみ本物の計算を行い、任意クエリ点は含まれる三角形の頂点から線形補間する。構築コストO(NM)、クエリコストO(1)を実現し、メモリベース手法の計算量問題を緩和する。