핏터웨이 삼각측량
Pitteway triangulation
계산 기하학에서 피트웨이 삼각측량은 삼각측량 내에서 임의의 점 p의 가장 가까운 이웃이 p를 포함하는 삼각형의 정점 중 하나인 점 집합 삼각측량이다.또는 각 내부 가장자리가 듀얼 보로노이 다이어그램 가장자리를 교차하는 딜라우나이 삼각측량이다.핏트웨이 삼각측량은 1973년 이를 연구한 마이클 핏트웨이의 이름을 딴 것이다.모든 점 집합이 피트웨이 삼각측량을 지원하는 것은 아니다.그러한 삼각형이 존재할 때는 델라우나이 삼각형의 특수한 경우로서 가브리엘 그래프와 볼록 선체의 결합으로 구성된다.
역사
핏테웨이 삼각측량 개념은 핏테웨이(1973년)가 도입했다."최적 파티션은 모든 삼각형 내의 점에 대해 해당 점이 다른 데이터 포인트와 마찬가지로 적어도 해당 삼각형의 꼭지점 중 하나에 가까운 파티션"을 쓰는 McLain(1976)도 참조하십시오."핏트웨이 삼각측량"이라는 이름은 오카베 외 연구원이 지어준 이름이다. (2000).
백작샘플
골드(1978)는 모든 점 집합이 피트웨이 삼각측량을 지원하는 것은 아니라고 지적한다.예를 들어, 일반 오각형의 삼각형은 삼각형 면 중 하나의 중간점 근처에 있는 점 p가 삼각형 바깥에 가장 가까운 이웃을 가질 수 있도록 중심 이소셀 삼각형을 포함한다.
기타 기하학적 그래프와의 관계
핏터웨이 삼각측정이 존재하는 경우, 삼각측량까지의 각 가장자리 내부의 중간점은 가장 가까운 이웃으로 두 개의 가장자리 끝점을 가져야 한다. 다른 이웃은 두 개의 인접한 삼각형 중 하나의 인근 지점에 대한 핏터웨이 특성을 위반할 수 있기 때문이다.따라서 그 가장자리를 직경으로 하는 원은 꼭지점이 비어 있어야 하므로 핏테웨이 삼각측량은 가브리엘 그래프로 점 세트의 볼록한 선체와 함께 구성된다.반대로 가브리엘 그래프와 볼록 선체가 함께 삼각측량을 형성하면 핏테웨이 삼각측량이다.
모든 가브리엘 그래프와 볼록한 선체 가장자리가 들로나이 삼각형의 일부분이기 때문에 핏트웨이 삼각측정이 존재했을 때 일반적인 위치의 점들에 대해 고유하며 들로나이 삼각측정과 일치한다.그러나 핏트웨이 삼각측정이 없는 점 집합에는 여전히 딜라우나이 삼각측정이 있을 것이다.
핏테웨이 삼각측량에서 각 에지 pq는 볼록 선체에 속하거나 p와 q를 포함하는 세포를 분리하는 보로노이 도표의 가장자리를 교차한다.일부 참조에서 이 속성은 모든 내부 Delaunay 가장자리가 이중 Voronoy 가장자리를 교차하는 Delaunay 삼각측량으로서 핏테웨이 삼각측량을 정의하는 데 사용된다.그러나 피트웨이 삼각측량은 이중선을 넘지 않는 볼록한 선체 가장자리를 포함할 수 있다.[1]
메모들
참조
- Dobrin, Adam (2005), A Review of Properties and Variations of Voronoi Diagrams (PDF), Whitman College
- 금, C.M.(1978년),"지리적 삼각 요소 데이터 구조의 실질적인 생성 및 사용"(PDF), 더튼에, G.(교육.), 저자들 제1회 국제 고급 연구 심포지엄 위상 데이터 구조물 지리 정보 시스템.하버드 기술 지리 정보 시스템에,:5— 데이터 구조물 vol..Surficial과 멀티차원., 보스턴:연구소 컴퓨터 그래픽스와 공간 분석, 하버드 대학, pp. 1–18.
- McLain, D. H. (1976), "Two dimensional interpolation from random data.", The Computer Journal, 19: 178–181, doi:10.1093/comjnl/19.2.178.
- Okabe, Atsuyuki; Boots, Barry N.; Chiu, Sung Nok; Sugihara, Kokichi (2000), Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, Wiley.
- Pitteway, M. L. V. (1973), "Computer graphics research in an academic environment", Datafair '73.
