정점 열거 문제

수학에서, 폴리토프, 다면체 셀 복합체, 초평면 배열, 또는 이산 기하학의 다른 물체에 대한 정점 열거 문제는 물체의 어떤 형식적인 표현이 주어졌을 때 물체의 정점을 결정하는 문제이다.전형적인 예는 선형 ^[1]부등식 집합에 의해 지정된 볼록 폴리토프의 정점 열거 문제이다.

${\displaystyle Ax\leq b}$

여기서 A는 m×n 행렬, x는 n×1 변수 열 벡터, b는 m×1 상수 열 벡터이다.주어진 정점이 주어진 경계 부등식을 찾는 역(이중) 문제를 패싯 열거라고 한다(볼록 껍질 알고리즘 참조).

계산의 복잡성

그 문제의 계산 복잡성은 컴퓨터 과학의 연구 주제이다.무한 다면체의 경우 문제는 NP-hard로 알려져 있으며, 보다 정확히는 P=NP가 ^[2]아닌 한 결합된 입출력 크기에서 다항 시간에 실행되는 알고리즘은 없습니다.

David Avis와 Komei^[3] Fukda의 1992년 논문은 d차원(또는 d차원에서의 n개 점의 볼록 선체의 v패싯, 각 패싯이 정확히 주어진 d개의 점을 포함하는)의 n개의 부등식에 의해 정의된 폴리토프의 v정점을 시간 O(ndv) 및 O(nd공간)에서 찾는 역서치 알고리즘을 제시한다.d차원에서 n개의 하이퍼플레인의 단순한 배열에 있는 v 정점은 O(ndv²) 시간과 O(nd) 공간의 복잡도에서 찾을 수 있다.Avis-후쿠다 알고리즘은 지향성 매트로이드에 대해 십자형 알고리즘을 채택했다.

메모들

레퍼런스

• Avis, David; Fukuda, Komei (December 1992). "A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra". Discrete and Computational Geometry. 8 (1): 295–313. doi:10.1007/BF02293050. MR 1174359.