최소 경계 상자 알고리즘

계산 기하학에서 가장 작은 상자 문제는 점 집합을 둘러싸는 방향의 최소 경계 상자를 찾는 것이다.그것은 일종의 경계 볼륨이다."소형"은 상자의 부피, 면적, 둘레 등을 가리킬 수 있다.

문제의 물체의 볼록한 선체를 위한 가장 작은 둘러싸인 상자를 찾기에 충분하다.좌표 축과 평행한 면이 있는 가장 작은 동봉 상자를 찾는 것은 간단하다. 문제의 어려운 부분은 상자의 방향을 결정하는 것이다.

2차원

볼록 폴리곤의 경우 최소 면적 둘러싸기 직사각형에 대한 선형 시간 알고리즘이 알려져 있다.그것은 최소 면적 둘러싸인 상자의 한 면이 볼록한 다각형의 한 면과 일직선이어야 한다는 관찰에 근거한다.^[1]1983년 고드프리드 뚜생에 의해 회전 캘리퍼스라고 불리는 접근법으로 이러한 종류의 박스를 선형적으로 열거할 수 있다.^[2]동일한 접근방식이 주변 사각형을 찾는 데 적용된다.^[2]

삼차원

1985년 조셉 오루르케는 3차원 점 세트의 최소 볼륨 동봉 상자를 찾기 위해 입방 시간 알고리즘을 발표했다.O'Rourke의 접근법은 3차원 회전 캘리퍼스 기법을 사용하며, 최소 둘러싸임 박스를 특징짓는 레마(lemmas)를 기반으로 한다.

• 둘 다 점 세트의 볼록한 선체의 가장자리를 포함하는 가장 작은 크기의 둘러싸인 상자의 인접 면 두 개가 있어야 한다.이 기준은 박스 가장자리와 볼록한 선체 가장자리 하나 또는 인접한 상자 면에 놓여 있는 두 개의 뚜렷한 선체 가장자리로 만족한다.
• 나머지 네 면에는 볼록한 선체의 점만 있으면 된다.다시 말하지만, 그들이 포함하고 있는 지점들은 구별될 필요가 없다: 상자의 구석에 놓여 있는 하나의 선체 지점은 이미 이 네 가지 기준 중 세 가지를 만족시키고 있다.

최소 둘러싸인 상자의 가장자리에 볼록한 선체 정점이 없는 가장 일반적인 경우, 적어도 8개의 볼록한 선체 지점이 상자의 면 안에 있어야 한다. 즉, 두 가장자리의 각 끝점 두 개와 나머지 네 개의 상자 면 각각에 하나씩 더 있어야 한다.반대로 볼록한 선체가 7개 이하의 정점으로 구성되면 그 중 적어도 하나는 선체의 최소 동봉 상자의 가장자리 안에 있어야 한다.^[3]

또한 최소 경계 상자 체적을 1보다 큰 상수 요인 내에서 선형 시간으로 근사할 수 있다.이를 위한 알고리즘에는 점 세트의 직경에 대한 근사치를 찾고, 최소 볼륨 경계 박스에 대한 초기 근사치로 이 직경을 지향하는 박스를 사용하는 것이 포함된다.그 후, 이 초기 경계 박스는 더 작은 정육면체의 격자로 분할되며, 입력의 볼록한 선체 경계 근처의 격자 지점은 코어 집합으로 사용되며, 이 점들의 집합은 최적의 경계 박스가 원래 입력의 최적 경계 박스에 근접한 작은 점들의 집합이다.마지막으로, 오루크의 알고리즘이 적용되어 이 코어 세트의 정확한 최적 경계 박스를 찾는다.^[4]

알고리즘의 Matlab 구현이 가능하다.^[5]

The minimal enclosing box of the regular tetrahedron is a cube, with side length 1/√2 that of the tetrahedron; for instance, a regular tetrahedron with side length √2 fits into a unit cube, with the tetrahedron's vertices lying at the vertices (0,0,0), (0,1,1), (1,0,1) and (1,1,0) of the unit cube.^[6]

참고 항목

• 가장 작은 동그라미 공
• 최소 경계 직사각형

참조