Convex Hull
이 글의 목차
← 기록 / 알고리즘 / 기하

Convex Hull

기하 문제에서 많이 쓰이는 볼록 껍질 알고리즘 Convex Hull에 관한 정리

기하 문제에서 많이 쓰이는 볼록 껍질 알고리즘 Convex Hull에 관한 정리

벡터의 외적

Math 카테고리에 따로 정리한 글이 있다.

Graham Scan

무려 O(n log n) 시간에 전체 볼록 껍질에 속하는 점들을 알아낼 수 있는 알고리즘이다. 벡터의 외적 성질을 아주 잘 활용한 알고리즘

작성 중

Monotone Chain

Graham Scan의 일종의 개선 판. 처음에 각도로 정렬하지 않아도 되기 때문에 좀 더 빠르다.

작성 중

활용 예

아래와 같은 문제들을 풀 수 있다.

  • 모든 점을 포함하는 최적의 다각형 구하기
  • 위 다각형이 통과하는 가장 작은 지름 구하기
  • 두 점 집단을 나눌 수 있는지 확인하기
  • 임의의 두 점 사이의 거리의 최대값
AI로 읽기 · Markdown
Markdown 열기 ↗
curl -fsSL 'https://www.readiz.com/notes/algorithm/geometry/convexhull/index.md'

서비스 열기

열기 방식을 선택해 주세요.

새 브라우저 탭에서 열기현재 화면을 유지하며 별도 탭에서 사용합니다.

로그인이 필요하거나 창 안에서 열리지 않는 서비스는 새 브라우저 탭에서 열어 주세요.