貪欲三角測量

貪欲三角測量
	ポリゴン貪欲三角分割のステップ。各ステップで、新しい辺（赤）が追加され、前の辺と交差することなく、最も近い頂点のペアを結合します。
クラス	検索アルゴリズム
データ構造	優先キュー; 空間データベース;
最悪の場合のパフォーマンス
最高のパフォーマンス

貪欲三角分割は、貪欲スキーマを使用して多角形三角分割または点集合三角分割を計算する方法であり、辺が以前に挿入された辺を切断できないという条件で、長さの厳密な増加順に辺を1つずつソリューションに追加します。^[1]^[2]

参考文献

^ J. Loera、J. Rambau、F. Santos (2010)、Triangulations: Structures and Algorithms (2nd改訂版)、Springer-Verlag、ISBN 9783642129711第3章: 多角形の三角形分割: pp.103。
^ Mark de Berg、Marc van Kreveld、Mark Overmars、およびOtfried Schwarzkopf (2000)、Computational Geometry (改訂第 2 版)、Springer-Verlag、ISBN 3-540-65620-0{{citation}}: CS1 maint: 複数の名前: 著者リスト (リンク)

貪欲三角測量
ポリゴン貪欲三角分割のステップ。各ステップで、新しい辺（赤）が追加され、前の辺と交差することなく、最も近い頂点のペアを結合します。
クラス	検索アルゴリズム
データ構造	優先キュー空間データベース
最悪の場合のパフォーマンス	$O(\|V\|\cdot \log \|V\|)$
最高のパフォーマンス	$O(\|V\|)$