Convex Hull 3D: 3차원 볼록 껍질

Convex Hull 3D, 3차원 볼록 껍질, 3D convex hull

정의

3D 점집합의 볼록 껍질: 모든 점을 포함하는 최소 볼록 다면체. 면 (face) 들이 삼각형으로 구성됨.

Incremental Construction

한 번에 한 점씩 추가:

1. 초기 정사면체 (일반 위치의 4 점)
2. 점 P 추가:
   • P 에서 보이는 (visible) 면 제거
   • 경계 (horizon) 를 따라 새 삼각형 부채 형성

O(N²) worst case, O(N log N) expected with random shuffle.

Gift Wrapping (3D)

각 면을 하나씩 “감싸” 나가는 방식. O(N · F), F = 면 개수. 정확하지만 느림.

Randomized Incremental (구현 편함)

무작위 셔플 + incremental 로 O(N log N) 기대 시간.

Chan’s Algorithm

O(N log H), H = 껍질 면 수. 이론적 최적.

응용

• 3D 물체의 최소 감싸는 다면체
• 최대 이격 두 점 (diameter)
• Voronoi diagram, Delaunay triangulation

참고

• 2D Convex Hull
• 3D Geometry