---
id: "imported/ps/algorithm/geometry/convexhull"
title: "Convex Hull"
description: "기하 문제에서 많이 쓰이는 볼록 껍질 알고리즘 Convex Hull에 관한 정리"
kind: "record"
published: "2023-05-31T00:00:00.000Z"
tags: ["algorithm","convex hull","geometry"]
url: "https://www.readiz.com/notes/algorithm/geometry/convexhull/"
markdownUrl: "https://www.readiz.com/notes/algorithm/geometry/convexhull/index.md"
---

# Convex Hull

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

## 벡터의 외적

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

- [벡터의 외적](https://www.readiz.com/blog/study/math/crossproduct/)

## Graham Scan

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

### 작성 중

## Monotone Chain

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

### 작성 중

## 활용 예

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

- 모든 점을 포함하는 최적의 다각형 구하기
- 위 다각형이 통과하는 가장 작은 지름 구하기
- 두 점 집단을 나눌 수 있는지 확인하기
- 임의의 두 점 사이의 거리의 최대값