많은 응용에서는 실제로 볼록 껍질 전체가 아니라 그 절반(오른쪽과 왼쪽, 또는 위쪽과 아래쪽)만 필요하며, 이를 포락선(영어: envelope)이라고 부릅니다.
엔벨로프를 구성하는 것은 조금 더 간단합니다: 점들을 $x$ 기준으로 정렬한 다음 그 순서대로 순회하면서, 현재 접두사에 대한 위쪽 엔벨로프를 스택에 유지하면 됩니다. 다음 점을 추가할 때는 마찬가지 방식으로 스택 맨 위의 점들을 몇 개 검사하고 제거해야 합니다:
vector<r> upper_envelope(vector<r> points) {
sort(points.begin(), points.end(), [](r a, r b){
return a.x < b.x;
});
vector<r> s = {p0};
for (r p : points) {
while (...) {
s[s.size()-2] = s[s.size()-1];
s.pop_back();
}
s.push_back(p);
}
return s;
}
엔벨로프는 전체 껍질보다 다루기 쉽습니다. 교차시키기, 합치기, 이진 탐색하기(예를 들어 접선을 찾기 위해)가 모두 쉽습니다. 참고로 합치기는 두 포인터로 두 껍질을 동시에 훑어 선형 시간에 수행할 수 있으며, 이를 이용하면 엔벨로프를 「분할 정복」 방식으로도 구성할 수 있고 이 역시 $O(n \log n)$에 동작합니다.
때로는 껍질을 두 개의 포락선으로 나누어 각각 따로 다루는 것이 합리적입니다. 이 방식의 주된 단점은 코드를 두 배로 많이 작성하거나, 모든 내부 프로시저가 “위"와 “아래"를 구별하지 않도록 코드를 작성해야 한다는 점입니다. 후자의 경우 $y_i$를 $-y_i$로 바꾸면 아래 포락선의 점들을 위 포락선과 같은 루틴에 그대로 넘길 수 있습니다.
또한 볼록 껍질을 구성하기 위해 다음과 같이 할 수도 있습니다. 위쪽 포락선을 구성하고, 아래쪽 포락선을 구성한 다음, 둘 중 하나를 뒤집어 다른 하나의 끝에 이어 붙입니다. 점들이 이미 $x$, $y$ 또는 다른 임의의 직선을 따라 정렬되어 있다면, 알고리즘은 $O(n)$에 동작합니다. 이러한 접근 방식을 앤드루 알고리즘이라고 합니다.
#동적 볼록 껍질
껍질을 두 개의 포락선으로 다루면, 포락선을 std::set이나 다른 임의의 트리에 담아 $x$ 기준으로 정렬된 상태가 되도록 함으로써 점 추가 쿼리를 비교적 간단하게 처리할 수 있습니다. 점을 추가할 때는 트리에서 그 점의 위치를 찾고, 그 점이 포락선보다 위에 있는지 확인한 뒤, 경우에 따라 그 점의 왼쪽 및 오른쪽 이웃 중 몇 개를 삭제해야 합니다.
집합에서 점의 삭제를 처리하는 것은 더 어렵습니다. 쿼리를 미리 알고 있다면, 제곱근 분할 또는 dynamic connectivity problem의 아이디어를 활용하여 현재 블록 전체에 걸쳐 존재하는 점들만 유지하고 삭제를 추가로 환원하는 것이 더 간단합니다.
삭제 쿼리를 온라인으로 처리해야 하는 경우(fully dynamic convex hull)에는 250-300줄의 코드로 이루어진 매우 까다로운 알고리즘이 있습니다. 이 알고리즘은 탐색 트리의 모든 서브트리에 대해 포락선을 유지하고, 트리를 재구성할 때 포락선을 빠르게 병합하는 방식입니다. 이 알고리즘은 쿼리당 $O(\log^2 n)$에 동작합니다. 정점을 합칠 때 포락선을 병합하는 과정에서 7가지 경우를 분석하는 이진 탐색이 사용됩니다.