비어 있는 가장 큰 직사각형

계산 기하학에서 가장 큰 빈 직사각형 문제,^[2] 최대 빈 직사각형 문제^[3] 또는 최대 빈 직사각형 문제는 평면의 장애물 사이에 놓일 최대 크기의 직사각형을 찾는 문제다.^[4]특히 "크기", 영역(장애물 유형), 사각형의 방향에 따라 이 일반적인 제형의 특수성에 따라 여러 가지 변형 문제가 있다.

이러한 종류의 문제는 예를 들어 전자 설계 자동화, 통합 회로의 물리적 배치 설계 및 검증에서 발생한다.^[5]

최대 빈 직사각형은 다른 빈 직사각형에 포함되지 않는 직사각형이다.최대 빈 직사각형의 각 면은 장애물을 피한다(그렇지 않으면 빈 직사각형을 증가시키면서 측면을 바깥쪽으로 이동시킬 수 있다).이러한 종류의 적용은 이미지 처리 및 패턴 인식의 이미지 분할 R&D에 "최대 흰색 사각형"을 열거하는 것이다.^[6]가장 큰 빈 직사각형에 대한 많은 알고리즘의 맥락에서, "최대 빈 직사각형"은 알고리즘이 고려해야 할 후보 솔루션이다. 예를 들어, 최대 영역 빈 직사각형이 최대 빈 직사각형임을 쉽게 입증하기 때문이다.

분류

크기 측정에 있어 가장 흔한 두 가지 경우는 가장 큰 면적의 빈 직사각형과 가장 큰 밀리미터의 빈 직사각형이다.^[7]

또 다른 주요 분류는 직사각형이 축 지향적인 직사각형 또는 임의 지향적인 직사각형 사이에서 추구되는지 여부다.

특례

최대 면적 제곱

추구하는 사각형이 축 지향적인 사각형인 경우 L ${\displaystyle {1\mathrm{}}_{}}$ ${\$1}의 해당 장애물 집합에$$ 대한 보로노이 도표를 사용하여 처리할 수 있으며, 이는 가장 큰 빈 원 문제와 유사하다.특히 사각형 내 점의 경우 시간 복잡도 $complexity{\displaystyle \mathrm{}(n}$ ${\displaystyle \log \mathrm{logn}}$ $){\displaystyle \Theta(n\log n)}$의 최적 알고리즘이 알려져$$ 있다.^[8]

도메인: 점을 포함하는 직사각형

1983년에^[1] Naamad, Lee, Hsu가 처음 논의한 문제는 다음과 같다: n개의 점을 포함하는 직사각형 A를 주어진다면, 주어진 점을 포함하지 않고 A의 직사각형과 평행한 가장 큰 면적의 직사각형을 찾아라.Naamad, Lee, Hsu는 시간 복잡성 $O{\displaystyle (min}$ ${\displaystyle (n{}^{}}$2 , s ${\displaystyle \log )n}$ $){\displaystyle$ O$(\min(n^{2},s\log n$의 알고리즘을 제시했는데, 여기서 s는 실현 가능한 해결책의 수, 즉, 최대 빈 직사각형이다.그들은 $또한{\displaystyle }$ s${\displaystyle }$= ${\displaystyle O}$( n ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle s=O(n^{2})}$라는 것을 증명하고$$ s가 n에서 2차인 예를 제시하였다. 그 후, 여러 논문에서 문제에 대한 더 나은 알고리즘을 제시하였다.

도메인: 선 세그먼트 장애물

동위원소 라인 세그먼트 중 빈 동위원소 직사각형의 문제는 1990년에 처음 고려되었다^[9].^[10]나중에 비시각 장애물들 사이에서 빈 동위원소 직사각형의 더 일반적인 문제가 고려되었다.^[9]

일반화

상위 치수

3차원 공간에서 알고리즘은 가장 큰 최대 빈 동위원소 큐보이드 문제를 찾아내는 것뿐만 아니라 모든 최대 동위원소 빈 큐보이드의 열거로도 알려져 있다.^[11]

참고 항목

• 가장 큰 빈 구체
• 최소 경계 상자, 최소 경계 사각형

참조