볼록 다포체
볼록 다포체(Convex Polytope)는 n차원 공간Rn에서 점들이 볼록 집합을 이루는 특성을 가진 특수한 다포체이다.[1] 다른 사람들은 다면체와 다포체의 표기에 차이를 두는 것을 선호하는 반면, 일부는 용어 "볼록 다포체"와 "볼록 다면체"를 교차적으로 사용한다..
게다가, 다른 문서들은[2] (이 문서를 포함해서) 무계여도 된다고 하지만, 일부 문서는 다포체가 유계 집합일 필요가 있다고 한다. 용어 "유계/무계 볼록 다포체"는 아레에서 논의된 문제에서 경계성이 중요할 때만 사용될 것이다. 하지만 다른 문서는 볼록 n다포체를 표면이나 (n-1)manifold로 다룬다.
볼록 다포체는 수학의 다양한 종류와 적용영역에서 중요한 역할을 한다. 선형 계획법에서 가장 유명하다.
볼록 다포체라고 불리는 주제에서 포괄적이고 영향력 있는 책은 1967년에 브랭코 그륀바움에 의해서 출판되었다. 2003년에는 새로운 저자들에 의해서 중요한 추가적인 자료를 포함한 두 번째 개정판이 출판되었다.[1]
그륀바움의 책과 이산기하학의 다른 책에서, 볼록 다포체를 자주 단순히 "다포체"라고 불렀다. 그륀바움은 이것은 단순히 "볼록"에 대한 무한한 순환 정의를 피하기 위한 것일 뿐이며, 여기서 나오는 것들은 볼록한 변형만으로 적용되는 것으로 이해해야 한다.
다포체가 Rn의 n차원 물체일 경우에는 full-dimensional이라고 부른다.
예시
[편집]- 유계 볼록 다포체는 "다면체" 문서에서 찾을 수 있다.
- 2차원의 경우에는 full-dimensional 예시는 반평면, 두 평행한 선 사이의 띠, 각 모양(두 평행하지 않은 반평면의 교차된 부분), 볼록 끝이 붙은 반직선 두 개로 이루어진 다각형 체인으로 정의되는 모양, 그리고 볼록 다각형이다.
- 무계 볼록 다포체의 특별한 경우는 평행한 초평면 두 개 사이의 넓적한 판, 두 개의 평행하지 않은 반공간으로 정의되는 쐐기꼴, 원기둥 (무한각기둥), 그리고 공통 점을 지나는 셋 이상의 반평면으로 정의된 볼록 원뿔 (무한 원뿔)이다.
정의
[편집]볼록 다포체는 문제에 적합한지에 따라서 다양한 방법으로 정의될 수 있다. 그륀바움은 공간에서 점들의 볼록 집합의 관점에서 정의했다. 다른 중요한 정의는: 반공간들의 교집합 (반공간 표기)과 점들의 집합의 볼록 폐포 (꼭짓점 표기)로 정의하는 것이다.
꼭짓점 표기 (볼록 폐포)
[편집]그의 책에서 볼록 다포체에 대해서, 그륀바움은 볼록 다포체를 유한한 개수의 극점을 가지는 콤팩트 볼록 집합:
- Rn의 집합 K는 모든 K의 구분되는 점 a,b의 쌍에 대해서, 양 끝점 a와 b를 포함하는 닫힌 선분이 K에 포함되어 있을 때, 볼록이다.
이것은 유계 볼록 다포체를 유한한 점 집합의 볼록 폐포로 정의하는 것과 동일하다. 그리고 유한한 집합은 반드시 다포체의 극점의 집합을 포함해야 한다. 이런 정의는 꼭짓점 표기 (V-표기 또는 V-해석)라고 부른다.[1] 콤팩트 볼록 다포체에 대해서, 최소 V-해석은 유일하고 다포체의 꼭짓점의 집합으로 주어진다.[1]
반공간의 교집합
[편집]볼록 다포체는 유한한 개수의 반공간의 교집합으로 정의할 수 있다. 이런 정의는 반공간 표기 (H-표기 또는 H-해석)라고 부른다.[1] 볼록 다포체의 H-해석은 무한히 많이 존재한다. 하지만, full-dimensional 볼록 다포체에 대해서, 최소 H-해석은 유일하고 반공간을 정의하는 facet의 집합으로 주어진다.[1]
이 때, n은 다루는 다포체를 포함하는 공간의 차원이다. 따라서, 닫힌 볼록 다포체는 다음 연립 일차 부등식의 솔루션의 집합으로 간주할 수 있다:
여기서 m은 다포체를 정의하는 반공간의 개수이다. 이것은 간단하게 행렬부등식으로 쓸 수 있다:
여기의 A는 m×n 행렬이고, x는 n×1 변수 열백터이며, b는 m×1 상수 열벡터이다.
열린 볼록 다포체는 같은 방법으로 엄밀하지 않은 것 대신에 엄밀한 부등식으로 정의된다.
A와 b의 각 행의 계수는 각각의 반공간을 정의하는 일차 부등식의 계수에 대응된다. 따라서 행렬의 각 행은 다포체를 포함하는 반공간의 경계인 지지 초평면과 대응한다. 지지 초평면이 다포체와 교차하면, 이것은 경계 초평면 (이것은 지지 초평면이기 때문에, 이것은 단순히 다포체의 경계에서 교차한다)이다.
앞의 정의는 다포체가 full-dimensional이라고 가정한다. 그렇지 않으면, Ax ≤ b의 솔루션은 적절한 아핀 공간 Rn에 생기며, 다포체에 관한 논의는 이 공간으로 제한된다.
일반적으로 대수 초평면의 교차첨은 유계일 필요는 없다. 하지만 볼록 폐포와 동일한 정의를 갖기를 원한다면 유계조건은 반드시 명시적으로 필요하다.
유한 기초 정리
[편집]유한 기초 정리[2]는 V-해석 표기법을 무한 다포체로 확장한 것이다. 이 정리는 볼록 다면체는 꼭짓점의 볼록 합 더하기 무한한 모서리의 방향 벡터의 원추 합이라고 기술한다.
같이 보기
[편집]각주
[편집]- ↑ 가 나 다 라 마 바 사 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.
- ↑ 가 나 Mathematical Programming, by Melvyn W. Jeter (1986) ISBN 0-8247-7478-7, p. 68
외부 링크
[편집]- Weisstein, Eric Wolfgang. “Convex polygon”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- Weisstein, Eric Wolfgang. “Convex polyhedron”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- Komei Fukuda, Polyhedral computation FAQ.