-
azberjibiou's profile image
azberjibiou
December 25, 2025
Happy ending problem
서론 Extremal Graph Theory의 핵심 질문은 “무질서해 보이는 구조가 충분히 크다면, 그 안에 특정한 패턴이 필연적으로 존재하는가?”이다. 본 글에서는 이러한 ‘필연적 질서’에 대한 논의를 1차원 수열에서 시작하여 2차원 기하 영역으로 확장한다. 구체적으로 Erdős-Szekeres Theorem을 통해 수열에서의 단조 부분 수열의 존재성을 증명하고, 이를 일반화하여 평면 기하학의 난제 중 하나였던 Happy Ending Problem과 볼록 다각형의 존재성에 대한 상한과 하한을 논한다. 1. Erdős-Szekeres Theorem Extremal Graph Theory의 논의를 시작하기 위해, 가장 기초적이면서도 강력한 정리를 소개한다. 이는 1차원 수열...
-
azberjibiou's profile image
azberjibiou
October 28, 2025
A game of cops and robbers on planar graph
A game of cops and robbers on planar graph “Cops and Robbers” 게임은 그래프 $G$ 상에서 정의되는 추격-회피 문제의 한 유형이다. 이 게임은 두 명의 플레이어, ‘Cop’ (C)와 ‘Robber’ (R)가 참여한다. 게임의 규칙은 다음과 같다. 먼저 Cop이, 그 다음 Robber가 그래프 상의 정점을 선택하여 위치한다. 이후 두 플레이어는 교대로 인접한 정점으로 이동한다. Cop이 Robber와 동일한 정점을 차지하게 되면 Cop의 승리로, Robber가 이러한 상황을 무한히 회피할 수 있다면 Robber의 승리로 규정된다. 본 논의는 Robber가 현재 위치에...
-
azberjibiou's profile image
azberjibiou
August 27, 2025
Lawson Algorithm을 통한 Delaunay triangulation 구하기
Lawson Algorithm을 통한 Delaunay triangulation 구하기 본 글은 평면 위 점들의 집합을 가장 안정적이고 균일한 삼각형들로 분할하는 Delaunay Triangulation을 종합적으로 탐구한다. 먼저 보로노이 다이어그램과의 관계 및 ‘빈 외접원 속성’을 통해 들로네 삼각분할의 수학적 정의를 명확히 하고, 이어서 고전적인 구축 방법인 Lawson’s algorithm을 분석한다. 마지막으로 이 알고리즘이 왜 항상 정확한 결과를 보장하는지를 증명하기 위해 2차원에서의 문제를 3차원으로 lifting하는 우아한 기법을 사용한다. 1. Delaunay triangulation의 정의와 최적성 평면에 분포된 유한한 점의 집합을 겹치지 않는 삼각형들로 분할하는 triangulation은...
-
azberjibiou's profile image
azberjibiou
July 24, 2025
Convex hull trick의 시간에 따른 관리
Convex Hull Trick의 시간에 따른 관리 Introduction Dynamic programming은 많은 문제에서 등장하는 풀이 방법이다. Convex hull trick은 $O(n^2)$ 시간복잡도를 $O(n log n)$으로 줄여주는 등 획기적인 시간 단축을 이루어내는 dynamic programming에 대한 최적화 방법이다. 이번 글에서는 시간에 따른 convex hull의 관리에 대해 알아본다. Persistent convex hull과 convex hull rollback에 대해서 알아보자. 1. Persistent Convex Hull 문제 상황 $n$개의 직선 $f_i(x) = a_ix + b_i$가 주어진다. 직선들의 기울기 $a_i$는 증가하는 순서로 주어진다. 쿼리로 주어진 $t$, $k$에 대해서...