볼록 집합이란 집합에 속한 임의의 두 점에 대하여, 그 두 점을 잇는 선분 위의 모든 점 역시 이 집합에 속하는 점들의 집합입니다.
점 집합의 볼록 껍질은 도형의 모든 점이 그 안에 포함되는 볼록 집합입니다.
점 집합의 최소 볼록 껍질은 넓이가 최소인 볼록 껍질입니다.
시간을 절약하기 위해 앞으로는 최소 볼록 껍질을 간단히 볼록 껍질이라고 부르겠습니다.
실용적인 관점에서 볼록 껍질이 유용한 이유는 점 집합에 대해 필요한 모든 정보를 간결하게 저장하므로, 이 집합에 대한 다양한 쿼리에 빠르게 답할 수 있기 때문입니다.
볼록 껍질은 어떤 공간에서든 생각할 수 있지만, 이 글에서는 2차원으로 한정하여 평면 위의 어떤 $n$개의 점 집합에 대해 볼록 껍질을 효율적으로 구성하는 방법과, 이를 이용해 그 집합에 대한 다양한 쿼리에 답하는 방법을 배우겠습니다.