The longest-edge bisection algorithm may produce degenerating tetrahedra

기술 요약: "최장변 이등분 알고리즘은 퇴화하는 사면체를 생성할 수 있다"

문제 정의
본 논문은 사면체 메쉬 세분화 이론의 결정적인 공백을 다룬다. 최장변 이등분(longest-edge bisection) 알고리즘은 중첩된 심플렉스 메쉬를 구축하기 위한 표준적인 기법이지만, 3차원에서의 비퇴화성(nondegeneration)에 관한 동작 방식은 완전히 이해되지 않았다. 2차원에서는 최장변 이등분을 반복하여 생성된 삼각형의 수렴성과 형상 규칙성(shape regularity)이 잘 확립되어 있다. 그러나 3차원에서는, 가장 긴 변을 이등분해야 하지만 여러 변의 길이가 같을 경우 임의의 변을 선택할 수 있는 제한 없는 기하학적 지침(unrestricted geometric instruction)은 비퇴화성을 보장하지 못한다. 기존 연구들은 표식된 모서리 방식(marked-edge schemes, 유한한 유사 클래스를 보장함)이나 특정 사면체 군(families)에 초점을 맞추어 왔으나, 임의의 동점 처리(tie-breaking)를 포함한 일반적인 무제한 규칙의 거동은 여전히 미해결 과제로 남아 있다.

방법론
저자는 무제한 규칙이 퇴화를 초래할 수 있음을 입증하기 위해 명시적이고 정확한 반례를 구성한다. 방법론은 다음과 같다:

1. 매개변수 군의 정의: 매개변수 $0 < a \le 1$에 의존하는 정점들을 가진 특정 사면체 $E(a)$를 정의한다.
2. 2단계 재귀 과정: 저자는 2단계 이등분 과정을 분석한다:
   • 1단계: $E(a)$의 유일한 최장변 $AD$를 이등분하고 자식 사면체 $O(a)$를 유지한다.
   • 2단계: $O(a)$에서 변 $BD$와 $DC$는 정확히 동일한 최장 길이를 갖는다. 저자는 $BD$를 이등분하도록 선택하고, 결과물인 자식 $F(a)$를 유지하며, 그 정점들의 이름을 다시 붙인다.
3. 정확한 합동 증명: 결과로 얻은 사면체 $F(a)$가 원래의 매개변수 군 $E(a/2)$와 합동임을 증명한다. 이는 매 두 번의 이등분 단계마다 형상 매개변수 $a$가 절반으로 줄어드는 재귀 관계를 확립한다.
4. 반복적 구성: $E(1)$로부터 시작하여, 이 과정은 무한한 사면체 수열 $E(1) \to O(1) \to E(1/2) \to O(1/2) \to \dots$를 생성한다.
5. 규칙성 분석: $a \to 0$ (여기서 $a_k = 2^{-k}$)인 경우에 대해 표준 규칙성 기준을 테스트하기 위해 정규화된 부피 비율($|T|/h_T^3$)과 특정 이면각을 계산한다.

주요 기여 및 결과
본 논문은 3차원의 무제한 최장변 이등분 알고리즘이 퇴화하는 사면체 수열을 생성할 수 있음을 엄밀하게 증명한다. 구체적인 결과는 다음과 같다:

• 형상 규칙성 위반: 정규화된 부피 비율 $|E_k|/h_{E_k}^3$은 $k \to \infty$일 때 0으로 수렴한다. 구체적으로, 이 비율은 $2^{-k/2}$로 점근적으로 감소하며, 이는 해당 군에 대해 유한한 양의 하한값이 존재하지 않음을 증명한다.
• 최소 각도 조건 위반: $E(a)$의 모서리 $CD$에서의 내부 이면각 $\delta(a)$는 0으로 수렴한다. 논문은 $\delta(a) \sim \sqrt{8a/7}$임을 보여주며, 이는 수열이 임의로 "납작한" 각도를 포함하고 있음을 의미한다.
• 최대 각도 조건 위반: $O(a)$의 모서리 $MC$에서의 내부 이면각 $\Theta(a)$는 $\pi$로 수렴한다. 이 각의 코사인 값은 $-1$에 접근하며, 이는 사면체가 다른 형태의 구성에서 임의로 "슬리버(sliver)와 같이 납작한" 상태가 됨을 나타낸다.
• 동점 처리의 역할: 퇴화는 최장변 길이의 반복적인 동점(tie, $BD = DC$)에 의해 발생한다. 논문은 결정론적인 동점 처리 규칙(더 긴 변의 반대편 변을 선택하는 것)이 이러한 "나쁜" 분기를 선택하는 데 충분함을 보여준다.

의의 및 주장
본 논문의 주요 주장은 겸손하지만 확고하다. 즉, 무제한 최장변 규칙 하에서 퇴화 가능한 허용 궤도(admissible orbit)의 존재를 증명한다는 것이다. 제목의 "may(할 수 있다)"라는 표현은 필수적이다. 이 구성은 모든 동점 처리 관습이 퇴화를 초래한다고 단언하거나, 모든 궤도가 퇴화한다고 주장하는 것이 아니다. 오히려, 알고리즘에 포함된 명시적인 동점 해결 메커니즘과 이를 규칙성 정리의 일부로 분석하지 않는다면, 알고리즘이 비퇴화 메쉬 생성을 보장하지 못한다는 것을 입증한다.

이 연구는 기하학적 선택 규칙만으로는 3차원 규칙성을 보장하기에 충분하다는 가정에 대한 반례 역할을 한다. 이는 3차원에서 세분화 동작이 표식(marking) 및 동점 처리(tie-breaking) 관습에 결정적으로 의존하며, 동일한 길이의 최장변들 사이의 임의적인 선택이 형상 규칙성, 최소 각도 경계, 그리고 최대 각도 경계의 동시 상실을 초래할 수 있음을 강조한다.