볼록한 선체: 컴퓨터 비전의 볼록 껍질(Convex Hull) 탐색

By Fouad Sabry

볼록 껍질이란 무엇입니까?

모양의 볼록 외피, 볼록 봉투 또는 볼록 마감은 모양을 포함하는 가장 작은 볼록 세트입니다. 이 개념은 기하학 분야에서 사용됩니다. 볼록 껍질은 두 가지 다른 방법으로 정의할 수 있습니다. 하나는 유클리드 공간의 특정 부분 집합을 포함하는 모든 볼록 집합의 교차점, 더 정확하게는 공간 내에 포함된 모든 볼록 점 조합의 집합입니다. 하위 집합. 평면의 경계가 있는 부분 집합의 볼록한 선체는 부분 집합 주위로 늘어나는 고무 밴드로 둘러싸인 형태로 볼 수 있습니다.

당신이 얻을 수 있는 혜택

(I) 다음 주제에 대한 통찰력 및 검증:

1장: 볼록 껍질

2장: 볼록 집합

3장: 다면체

4장: 폴리토프

5장: 민코프스키 덧셈

6장: 이중성(수학)

7장: 카라테오도리의 정리(볼록 껍질)

8장: 곡선적 관점

9장: 라돈의 정리

10장: 볼록다포체

(II) 볼록 껍질에 관한 대중의 주요 질문에 답합니다.

(III) 다양한 분야에서 볼록 껍질을 사용하는 실제 사례.

이 책은 누구를 위한 책인가

전문가, 학부 및 대학원생, 매니아, 취미생활자 및 모든 종류의 볼록한 선체 에 대한 기본 지식이나 정보를 넘어서고 싶은 사람들.

• Language: 한국어
• Publisher: 10 억 지식이 걸립니다 [Korean]
• Release date: May 5, 2024

Book preview

챕터 1: 볼록 껍질

기하 도형에서 도형의 볼록 껍질, 볼록 엔벨로프 또는 볼록 클로저는 도형을 포함하는 가장 작은 볼록 세트입니다. 볼록 껍질은 유클리드 공간의 특정 하위 집합을 포함하는 모든 볼록 집합의 교차점 또는 하위 집합의 모든 볼록 조합의 집합으로 정의 될 수 있습니다. 평면의 경계가 있는 부분 집합의 경우 볼록 껍질은 확장된 고무 밴드에 포함된 형태로 볼 수 있습니다.

개방형은 개방된 세트의 볼록한 껍질이며, 컴팩트 세트에는 컴팩트한 볼록한 껍질이 있습니다.

각 볼록한 컴팩트 세트는 사지의 볼록한 껍질입니다.

볼록 껍질 연산자는 폐쇄 연산자의 예이며, 모든 antimatroid는 이 폐쇄 연산자를 유한 점 집합에 적용하여 나타낼 수 있습니다.

평면 또는 기타 저차원 유클리드 공간에서 유한한 수의 점의 볼록 껍질을 찾는 것은 알고리즘 문제를 제시하며, 반공간이 겹치는 이중적 문제는 필수적인 계산 기하학 문제입니다.

2차원 또는 3차원 점 집합에 대해 시간 내에 해결할 수 있으며, 더 높은 차원에서 상한 정리에 의해 주어진 최악의 경우 출력 복잡도와 일치하는 시간 내에 O(n\log n) 해결할 수 있습니다.

볼록 선체는 유한점 집합 외에도 단순 다각형, 브라운 운동, 공간 곡선 및 함수의 에피그래프에 대해서도 탐구되었습니다. 수학, 통계, 조합 최적화, 경제학, 기하학적 모델링 및 행동학에서 볼록한 껍질은 다양한 용도로 사용됩니다. 볼록 두개골, 직교 볼록 껍질, 볼록 레이어, 들로네 삼각분할, 보로노이 다이어그램은 관련 구조입니다.

유클리드 공간의 점 모음은 각 점 쌍을 연결하는 선분을 포함하는 경우 볼록합니다.

주어진 세트의 볼록 껍질은 X 다음과 같이 정의될 수 있습니다.

다음을 포함하는 (고유한) 최소 볼록 집합 X

다음을 포함하는 모든 볼록 집합의 교집합 X

에 있는 점의 모든 볼록 조합 집합입니다. X

모든 단순성과 정점의 합집합 X

단일 선이 아닌 유클리드 평면에서 제한되는 집합의 경우 볼록 껍질의 경계는 를 포함하는 최소 둘레가 있는 단순 닫힌 곡선입니다 X .

고무줄을 늘려 전체 세트를 둘러쌌 S 다가 풀어 놓으면 수축하는 것을 상상할 수 있습니다. 고무줄이 조여지면 의 볼록한 선체를 감쌉 니다 S .

3차원 객체의 경우 볼록 껍질의 초기 정의는 가능한 가장 작은 볼록 경계 볼륨으로 지정합니다. 볼록 집합의 교차점을 사용하는 정의는 비유클리드 기하학으로 확장될 수 있으며, 볼록 조합을 사용하는 정의는 유클리드 공간에서 임의의 실수 벡터 공간 또는 아핀 공간으로 확장될 수 있습니다. 볼록한 선체는 또한 방향성 매트로이드로 추상적으로 일반화될 수 있습니다.

첫 번째 정의가 의미가 있다는 것은 분명하지 않습니다 : 왜 모든 것에 대해 , 를 포함하는 고유 한 최소 볼록 집합이 있어야합니까 X X ? 그러나 두 번째 의미인 를 포함하는 모든 볼록 집합의 교집합 X 은 명확하게 정의되어 있습니다.

교차되는 집합에 포함되기 Y 때문에 를 X 포함하는 Y 다른 모든 볼록 집합의 하위 집합입니다.

따라서 정확히 를 포함하는 고유한 최소 볼록 집합입니다 X .

따라서 처음 두 정의는 동일합니다.

를 포함하는 각 볼록 집합 X 은 (볼록하다고 가정할 때) 에 있는 점의 모든 볼록 조합을 포함해야 X 하므로 모든 볼록 조합의 집합은 를 포함하는 모든 볼록 집합의 교차점에 포함됩니다 X .

반대로, 모든 볼록 조합의 집합은 그 자체로 를 포함하는 볼록 집합이므로 X 를 포함하는 모든 볼록 집합의 교집합도 포함 X 하므로 두 번째 및 세 번째 정의는 동일한 의미를 갖습니다.

사실, Carathéodory의 정리에 따르면,  가 -차원 유클리드 공간 X 의 부분 집합인 d 경우, 에서 유한하게 많은 점의 모든 볼록 조합 X 은 의 대부분의 점의 볼록 조합이기도 합니다 d+1 X .

-tuple of points의 볼록한 조합 집합 (d+1) 은 심플렉스입니다. 2차원에서는 삼각형이고 3차원에서는 사면체입니다.

따라서 점의 모든 볼록 조합 X 은 꼭짓점이 X 세 번째 및 네 번째 정의와 같은 에 속하는 심플렉스에 속합니다.

2차원에서 볼록한 선체는 때때로 선체의 가장 왼쪽과 가장 오른쪽 지점에서 확장되는 상부 선체와 하부 선체의 두 부분으로 나뉩니다. 일반적으로 모든 차원의 볼록 선체의 경계는 위쪽을 향하는 점(위쪽 광선이 선체에서 불연속적인 점), 아래쪽을 향한 점 및 극한 점으로 나눌 수 있습니다. 3차원 선체에 대한 경계의 위쪽과 아래쪽을 향한 부분은 위상 디스크를 형성합니다.

세트의 닫힌 볼록 선체는 볼록 선체의 폐쇄이며, 열린 볼록 선체는 볼록 선체의 내부 (또는 일부 소스에서는 상대적 내부)입니다.

의 닫힌 볼록 껍질 X 은 를 포함하는 모든 닫힌 반쪽 공간의 교집합입니다 X .

의 볼록 껍질 X 이 이미 닫힌 집합 자체인 경우(예를 들어, X 유한 집합 또는 더 일반적으로 콤팩트 집합인 경우) 결과적으로 닫힌 볼록 껍질과 동일합니다.

그러나 반공간의 닫힌 교차점은 그 자체로 닫혀 있으므로 닫히지 않은 볼록 껍질은 이러한 방식으로 표현할 수 없습니다.

집합의 열린 볼록 껍 질 X 이 d -dimension인 경우 껍질의 모든 점은 의 대부분의 점에서 열린 볼록 껍질에 속 2d 합니다 X .

정사각형의 꼭짓점, 정팔면체 또는 고차원 교차 다중정점의 집합은 정확히 2d 점이 필요한 예를 제공합니다.

열린 집합의 볼록 껍질은 위상 학적 관점에서 항상 열려 있는 반면, 컴팩트 세트의 볼록 껍질은 항상 그 자체로 컴팩트합니다. 그러나 볼록한 껍질이 닫히지 않은 닫힌 세트가 있습니다. 구체적으로, 닫힌 집합

{\displaystyle \left\{(x,y)\mathop {\bigg |} y\geq {\frac {1}{1+x^{2}}}\right\}}

의 볼록한 선체(아그네시의 마녀 위 또는 위에 있는 점들의 집합)는 열린 상반면이다.

볼록 집합의 극점은 집합의 다른 두 점 사이의 열린 선분에 놓이지 않는 점입니다. 볼록 껍질의 모든 극점은 제공된 세트에 포함되어야 합니다. 그렇지 않으면 지정된 점의 볼록 조합으로 만들 수 없습니다. 유클리드 공간(또는 더 일반적으로 국소적으로 볼록한 위상 벡터 공간)에 설정된 모든 조밀한 볼록은 Krein-Milman 정리에 따라 극점의 볼록 껍질입니다.

볼록한 껍질 연산자는 클로저 연산자의 특성을 가지고 있습니다.

이는 상당하며, 이는 모든 세트의 볼록 껍질 X 이 의 상위 집합임을 의미합니다 X .

이 값은 감소하지 않으며, 이는 두 세트마다 X Y X\subseteq Y 의 볼록 껍질 X 이 의 볼록 껍질의 부분 집합임을 의미합니다 Y .

그것은 되돌릴 수 없으며, 모든 에 대해 X 의 볼록 선체의 볼록 선체 X