탐욕스러운 삼각 측량

Greedy triangulation
탐욕스러운 삼각 측량
Polygon Greedy triangulation steps
폴리곤 탐욕스러운 삼각 측량 단계입니다.각 단계에서 이전 모서리를 교차하지 않고 가장 가까운 정점 쌍을 연결하는 새 모서리(빨간색)가 추가됩니다.
학급검색 알고리즘
data 구조
최악의 경우 성능
베스트 케이스 성능

Gready Triangulation은 Gready 스키마를 사용하여 폴리곤 삼각 측량 또는 점 집합 삼각 측량을 계산하는 방법입니다. 이 스키마는 길이별로 엄밀한 증가 순서로 에지를 하나씩 솔루션에 추가합니다. 단, 에지는 이전에 삽입된 [1][2]에지를 절단할 수 없습니다.

레퍼런스

  1. ^ J. Loera, J. Rambau and F. Santos (2010), Triangulations: Structures and Algorithms (2nd revised ed.), Springer-Verlag, ISBN 9783642129711 3장: 폴리곤 삼각 측량: 페이지 103.
  2. ^ Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised ed.), Springer-Verlag, ISBN 3-540-65620-0{{citation}}: CS1 maint: 여러 이름: 작성자 목록(링크)