-
Lawson Algorithm을 통한 Delaunay triangulation 구하기
Lawson Algorithm을 통한 Delaunay triangulation 구하기 본 글은 평면 위 점들의 집합을 가장 안정적이고 균일한 삼각형들로 분할하는 Delaunay Triangulation을 종합적으로 탐구한다. 먼저 보로노이 다이어그램과의 관계 및 ‘빈 외접원 속성’을 통해 들로네 삼각분할의 수학적 정의를 명확히 하고, 이어서 고전적인 구축 방법인 Lawson’s algorithm을 분석한다. 마지막으로 이 알고리즘이 왜 항상 정확한 결과를 보장하는지를 증명하기 위해 2차원에서의 문제를 3차원으로 lifting하는 우아한 기법을 사용한다. 1. Delaunay triangulation의 정의와 최적성 평면에 분포된 유한한 점의 집합을 겹치지 않는 삼각형들로 분할하는 triangulation은...
-
Relevant points in Nearest-Neighbor Classification
Introduction $k$-nearest neighbor classification이란, $d$차원 공간 위의 point cloud들 (training set)과 그 class가 주어져 있을 때, 새로운 점의 class를 예측하는 한 가지 방법입니다. 자신과 가장 가까운 $k$개의 점의 label 중 가장 많은 것을 선택하는 방법으로, 고전적인 pattern recognition method 중 하나로 소개되었습니다. 오늘은 이 중 그나마 알고리즘의 시각에서 조명이 가능한 $k = 1$ case, 즉, nearest-neighbor classification에 대해 알아봅시다. 1-NN classification and Voronoi diagram $d = 2$인 경우, 어떤 점 $p$의 nearest neighbor가 $q$일 필요충분조건은...
-
Fast Polygon Triangulation
Table Of Contents Introduction Preliminaries Degeneracy Strict Total Order Monotone Polygon Montone Polygon Triangulation Example Polygon Triangulation Boundary Vertex Classification Sweepline Events Example Implementation Introduction 안녕하세요, Aeren입니다! Polygon triangulation은 classical한 computational geometry problem중 하나로, 어떤 simple polygon의 boundary가 counterclockwise하게 주어질 때, triangulation을 찾는 문제입니다. 이번 글에서 소개할 내용은 $N$을 polygon의 vertex 갯수라고 할 때 $O(N \log N)$시간 안에 위 문제를 해결하는 알고리즘입니다. 참고로 이 문제는 $O(N)$시간 안에 해결 가능함이 알려져 있습니다. (참조) Preliminaries Degeneracy 이...