볼록 다포체 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:3dpoly.svg|섬네일|오른쪽|3차원 볼록 다포체]]
'''볼록 다포체'''(Convex Polytope)는 ''n''차원 공간'''R'''<sup>''n''</sup>에서 점들이 [[볼록 집합]]을 이루는 특성을 가진 특수한 [[다포체]]이다.<ref name=grun/> 다른 사람들은 [[다면체]]와 다포체의 표기에 차이를 두는 것을 선호하는 반면, 일부는 용어 "볼록 다포체"와 '''"볼록 다면체"'''를 교차적으로 사용한다..

게다가, 다른 문서들은<ref name=Jeter>''Mathematical Programming'', by Melvyn W. Jeter (1986) {{ISBN|0-8247-7478-7}}, [https://books.google.com/books?id=ofrBsl61lq8C&pg=PA67 p. 68]</ref> (이 문서를 포함해서) 무계여도 된다고 하지만, 일부 문서는 다포체가 [[유계 집합]]일 필요가 있다고 한다. 용어 "유계/무계 볼록 다포체"는 아레에서 논의된 문제에서 경계성이 중요할 때만 사용될 것이다. 하지만 다른 문서는 볼록 ''n''다포체를 표면이나 (''n''-1)manifold로 다룬다.

볼록 다포체는 [[수학]]의 다양한 종류와 적용영역에서 중요한 역할을 한다. [[선형 계획법]]에서 가장 유명하다.

''볼록 다포체''라고 불리는 주제에서 포괄적이고 영향력 있는 책은 1967년에 [[브랭코 그륀바움]]에 의해서 출판되었다. 2003년에는 새로운 저자들에 의해서 중요한 추가적인 자료를 포함한 두 번째 개정판이 출판되었다.<ref name=grun/>

그륀바움의 책과 [[이산기하학]]의 다른 책에서, 볼록 다포체를 자주 단순히 "다포체"라고 불렀다. 그륀바움은 이것은 단순히 "볼록"에 대한 무한한 순환 정의를 피하기 위한 것일 뿐이며, 여기서 나오는 것들은 볼록한 변형만으로 적용되는 것으로 이해해야 한다.

다포체가 '''R'''<sup>''n''</sup>의 ''n''차원 물체일 경우에는 ''full-dimensional''이라고 부른다.

== 예시 ==
* 유계 볼록 다포체는 "[[다면체]]" 문서에서 찾을 수 있다.
* 2차원의 경우에는 full-dimensional 예시는 [[반평면]], 두 평행한 선 사이의 띠, [[각 (수학)|각]] 모양(두 평행하지 않은 반평면의 교차된 부분), 볼록 끝이 붙은 [[반직선]] 두 개로 이루어진 [[다각형 체인]]으로 정의되는 모양, 그리고 [[볼록 다각형]]이다.
* 무계 볼록 다포체의 특별한 경우는 평행한 초평면 두 개 사이의 넓적한 판, 두 개의 평행하지 않은 [[반공간]]으로 정의되는 쐐기꼴, [[원기둥]] (무한[[각기둥]]), 그리고 공통 점을 지나는 셋 이상의 반평면으로 정의된 [[볼록 원뿔]] (무한 [[원뿔]])이다.

== 정의 ==

볼록 다포체는 문제에 적합한지에 따라서 다양한 방법으로 정의될 수 있다. 그륀바움은 공간에서 점들의 볼록 집합의 관점에서 정의했다. 다른 중요한 정의는: [[반공간]]들의 [[교집합]] (반공간 표기)과 점들의 집합의 [[볼록 폐포]] (꼭짓점 표기)로 정의하는 것이다.

=== 꼭짓점 표기 (볼록 폐포) ===

그의 책에서 ''볼록 다포체''에 대해서, 그륀바움은 볼록 다포체를 '''유한한 개수의 [[극점 (기하학)|극점]]을 가지는 [[콤팩트 공간|콤팩트]] [[볼록 집합]]''':
: '''R'''<sup>''n''</sup>의 집합 ''K''는 모든 ''K''의 구분되는 점 ''a'',''b''의 쌍에 대해서, 양 끝점 ''a''와 ''b''를 포함하는 닫힌 선분이 ''K''에 포함되어 있을 때, ''볼록''이다.

이것은 유계 볼록 다포체를 유한한 점 집합의 [[볼록 폐포]]로 정의하는 것과 동일하다. 그리고 유한한 집합은 반드시 다포체의 극점의 집합을 포함해야 한다. 이런 정의는 '''꼭짓점 표기''' ('''V-표기''' 또는 '''V-해석''')라고 부른다.<ref name=grun/> 콤팩트 볼록 다포체에 대해서, 최소 V-해석은 유일하고 다포체의 [[꼭짓점]]의 집합으로 주어진다.<ref name=grun/>

=== 반공간의 교집합 ===

볼록 다포체는 유한한 개수의 반공간의 교집합으로 정의할 수 있다. 이런 정의는 '''반공간 표기''' ('''H-표기''' 또는 '''H-해석''')라고 부른다.<ref name=grun/> 볼록 다포체의 H-해석은 무한히 많이 존재한다. 하지만, full-dimensional 볼록 다포체에 대해서, 최소 H-해석은 유일하고 반공간을 정의하는 [[facet]]의 집합으로 주어진다.<ref name=grun/>

[[닫힌 반공간]]은 [[일차 부등식]]으로 쓸 수 있다:<ref name=grun>[[Branko Grünbaum]], ''Convex Polytopes'', 2nd edition, prepared by [[Volker Kaibel]], [[Victor Klee]], and [[Günter M. Ziegler]], 2003, {{ISBN|0-387-40409-0}}, {{ISBN|978-0-387-40409-7}}, 466pp.</ref>

:<math>a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \leq b</math>

이 때, ''n''은 다루는 다포체를 포함하는 공간의 차원이다. 따라서, '''닫힌 볼록 다포체'''는 다음 [[연립 일차 부등식]]의 솔루션의 집합으로 간주할 수 있다:

:<math>\begin{alignat}{7}
a_{11} x_1 &&\; + \;&& a_{12} x_2 &&\; + \cdots + \;&& a_{1n} x_n &&\; \leq \;&&& b_1      \\
a_{21} x_1 &&\; + \;&& a_{22} x_2 &&\; + \cdots + \;&& a_{2n} x_n &&\; \leq \;&&& b_2      \\
\vdots\;\;\; &&     && \vdots\;\;\; &&              && \vdots\;\;\; &&     &&& \;\vdots \\
a_{m1} x_1 &&\; + \;&& a_{m2} x_2 &&\; + \cdots + \;&& a_{mn} x_n &&\; \leq \;&&& b_m      \\
\end{alignat}</math>

여기서 ''m''은 다포체를 정의하는 반공간의 개수이다. 이것은 간단하게 [[행렬]]부등식으로 쓸 수 있다:

:<math>Ax \leq b</math>

여기의 ''A''는 ''m''×''n'' 행렬이고, ''x''는 ''n''×1 변수 열백터이며, ''b''는 ''m''×1 상수 열벡터이다.

'''열린 볼록 다포체'''는 같은 방법으로 엄밀하지 않은 것 대신에 엄밀한 부등식으로 정의된다.

''A''와 ''b''의 각 행의 계수는 각각의 반공간을 정의하는 일차 부등식의 계수에 대응된다. 따라서 행렬의 각 행은 다포체를 포함하는 반공간의 경계인 '''지지 초평면'''과 대응한다. 지지 초평면이 다포체와 교차하면, 이것은 '''경계 초평면''' (이것은 지지 초평면이기 때문에, 이것은 단순히 다포체의 경계에서 교차한다)이다.

앞의 정의는 다포체가 full-dimensional이라고 가정한다. 그렇지 않으면, ''Ax'' ≤ ''b''의 솔루션은 적절한 [[아핀 공간]] '''R'''<sup>''n''</sup>에 생기며, 다포체에 관한 논의는 이 공간으로 제한된다.

일반적으로 대수 초평면의 교차첨은 유계일 필요는 없다. 하지만 볼록 폐포와 동일한 정의를 갖기를 원한다면 유계조건은 반드시 명시적으로 필요하다.

==== 유한 기초 정리 ====

'''유한 기초 정리'''<ref name=Jeter/>는 V-해석 표기법을 무한 다포체로 확장한 것이다. 이 정리는 볼록 다면체는 꼭짓점의 [[볼록 합]] 더하기 무한한 모서리의 [[방향 벡터]]의 [[원추 합]]이라고 기술한다.

== 같이 보기 ==
* [[원점 매트로이드]]
* [[네프 다면체]]

== 각주 ==
{{각주}}

== 외부 링크 ==
{{위키공용분류}}
* {{매스월드| urlname = ConvexPolygon | title = Convex polygon}}
* {{매스월드| urlname = ConvexPolyhedron | title = Convex polyhedron}}
* [[Komei Fukuda]], [https://web.archive.org/web/20080629235600/http://www.ifor.math.ethz.ch/~fukuda/polyfaq/polyfaq.html Polyhedral computation FAQ].

{{전거 통제}}

[[분류:다포체]]
[[분류:볼록기하학]]