불투명 집합

이산형 기하학에서 불투명 집합은 다각형, 원 또는 기타 형상에 걸쳐 모든 가시선을 차단하는 곡선 또는 평면의 다른 집합의 시스템이다. 불투명 집합은 장벽, 빔 검출기 또는 (선 세그먼트 숲의 형태를 갖는 경우) 불투명 숲이라고도 불린다. 불투명 세트는 1916년 스테판 마주르키에비츠에 의해 도입되었고,^[1] 총 길이 최소화 문제는 1959년 프레데릭 베이그미흘에 의해 제기되었다.^[2]

예를 들어 단위 사각형을 통한 가시성은 길이 4의 네 경계 가장자리로 차단할 수 있지만 길이가 $2{\displaystyle \sqrt{\mathrm{}}}$+ ${\displaystyle 1\frac{\mathrm{}}{}}$ 2 ${\displaystyle 6\sqrt{\mathrm{}}}$ ${\displaystyle \approx }$ 2${\displaystyle {\sqrt{2}}+{\tfrac{1$}{$1}{{\sqrt{6}}}\ 약 2.$639}인 사각형 전체에 걸쳐 짧은 불투명 숲이 가시성을 차단할 수 있다$.$ 이것이 가장 짧은지는 검증되지 않았다. 정사각형을 위해 설정되고, 대부분의 다른 형태에서도 마찬가지로 이 문제는 해결되지 않은 채로 남아 있다. 평면에 있는 경계 볼록 세트의 가장 짧은 불투명 세트는 세트 둘레의 길이가 대부분이고 둘레의 절반 이상이 된다. 사각형의 경우 둘레의 절반보다 약간 더 강한 하한선이 알려져 있다. 불투명한 세트가 일반적으로 연구되는 또 다른 볼록 세트는 단위 원이며, 가장 짧은 연결 불투명 세트는 $길이{\displaystyle \mathrm{}}$2 + ${\displaystyle \pi }$ ${\displaystyle$ 2$+\pi$}을(를) 가지고 있다$.$ 연결을 가정하지 않고 원의 가장 짧은 불투명 세트는 길이가 $최소{\displaystyle }$ { ${\displaystyle \pi$}, 최대$$ 4.7998이다.

볼록 폴리곤에 대한 가장 짧은 불투명 집합을 찾는다고 주장하는 몇몇 발표된 알고리즘은 나중에 부정확한 것으로 나타났다. 그럼에도 불구하고, 선형 시간에서 보장된 근사비를 가진 불투명 집합을 찾거나, 다항 시간에서 주어진 선 세그먼트 시스템에 의해 가시성이 차단되는 평면의 부분집합을 계산할 수 있다.

정의들

$평면$의 모든 세트$$ $S{\displaystyle }$ ${\displaystyle S},$ 그 $범위{\displaystyle }$ C ${\displaystyle$ $C$$$C ${\displaystyle$ C$},$ $점$을 통과하는 모든 선이 S ${\\displaystyle S}$을 교차하는 점으로 구성된다$.$ 주어진 세트 $K{\displaystyle }$ ${\displaystyle K}$이 하위 집합을 형성하는$$ 경우 S ${\displaystyle S$$}$의 적용 $범위$는 K ${\displaystyle$ $K$$}$에 대한 불투명 세트, 장벽 또는 빔 검출기로 알려져$$ 있다$.$ 추가적으로 S ${\displaystyle S}$은 특별한 형태를 가지고$$ 있으며, 결합이 숲을 이루는 선 세그먼트로 구성된다. $K{\displaystyle }$ ${\displaystyle K}$ 자체를$$ 포함하여$$모든 $특정{\displaystyle }$ 세트$$K {\$displaystyle$ K}에 대해 가능한 불투명 세트와 많은 불투명 숲이 있다. 불투명한 숲의 경우, 또는 보다 일반적으로 수정 가능한 곡선의 시스템에 대해서는 길이가 표준적인 방법으로 측정될 수 있다. 보다 일반적인 점 세트의 경우 1차원 Hausdorff 측정을 사용할 수 있으며, 선 세그먼트 및 정류 가능한 곡선의 경우 표준 길이와 일치한다.^[3]

이 문제에 대한 대부분의 연구는 주어진 세트 $K{\displaystyle }$ ${\$디스플레이 $스타일$ K$}$이(가) 볼록 세트라고 가정한다. 볼록한 것이 아니라 단지 연결된 세트일 때 불투명 세트를 바꾸지 않고 볼록한 선체로 교체할 수 있다. 문제의 일부 변형에서는 불투명한 세트가 $K{\displaystyle }${\$displaystyle K}$의 내부 또는 외부에 완전히 놓여지도록 제한한다$.$ 이 경우 각각 내부 배리어 또는 외부 장벽으로 불린다. 이것이 명시되지 않은 경우, 장벽은 그 위치에 제약이 없는 것으로 가정한다. 불투명 세트가 연결되거나 단일 곡선을 형성해야 하는 문제의 버전도 고려되었다. 모든 볼록 세트 $P{\displaystyle }$ ${\displaystyle P}$이(가) 최단 불투명 세트를 가지고$$ 있는지 또는 그 대신 불투명한 세트의 길이가 이에 도달하지 않고 최소치에 근접할 수 있는지 여부는 알려지지 않았다.^[3] $P{\displaystyle }$ ${\displaystyle P}$에 대한 모든 불투명 세트는 불투명한 숲에 의해 임의로 길이에 가깝게 대략적으로 추정할$$ 수 있으며,^[4] 모든 볼록 폴리곤에는 불투명 숲이 최단 불투명 세트로 존재한다고 추측되어 왔지만, 이는 입증되지 않았다.^[3]

경계

커버할 영역이 볼록한 집합인 경우, 가장 짧은 불투명 집합의 길이는 둘레의 절반 이상과 최대 둘레가 되어야 한다. 일부 지역의 경우 이러한 한계에 대한 추가 개선이 이루어질 수 있다.

상한

$K{\displaystyle }$ ${\displaystyle K}$이(가) 포함되어야 하는 경계 볼록 세트인$$ 경우 경계${\displaystyle \mathrm{}\mathrm{boundary}}$ K ${\displaystyle \partial$ K$}$은(는) 불투명한 세트를 형성하며$$, 길이는 둘레 ${\displaystyle \partial \mathrm{}}$ ${\displaystyle K}$ $displaystyle \partial K}$이므로 불투명 세트의 가장 짧은 길이는 대부분의 둘레에 있다$.$ 경계에는 선 세그먼트가 없음을 의미하는 볼록하게$$ $볼록한{\displaystyle }$세트 K {\$displaystyle$K}의 경우, 그리고 내부 장벽의 경우 이 바운드가 촘촘하다. 모든 경계점은 다른 점으로 차단할 수 없는 접선선을 통과하기 때문에 경계의 모든 점들은 불투명한 집합에 포함되어야 한다.^[5] 같은 추론은 볼록 폴리곤의 내부 장벽의 경우 모든 정점이 포함되어야 한다는 것을 보여준다. 따라서 정점의 최소 슈타이너 트리는 최단 연결 불투명 집합이고, 정점의 이동 판매원 경로는 최단 단곡선 불투명 집합이다.^[4] 단, 엄격히 볼록하지 않은 비폴리곤 볼록한 집합의 내부 장벽이나 연결할 필요가 없는 장벽의 경우 다른 불투명 집합은 더 짧아질 수 있다. 예를 들어, 경계에서 가장 긴 선 세그먼트를 생략하는 것이 항상 가능하다. 이 경우 둘레 또는 스타이너 트리 길이는 불투명 집합의 길이에 상한을 제공한다.^[3][4]

하한

볼록 세트 $K{\displaystyle }$ ${\displaystyle K}$에 대한 불투명 세트의 총 길이는 둘레의 ${\displaystyle \mathrm{절반}}$인$$${\displaystyle \partial \mathrm{}}$ K${\displaystyle }$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle \partial K /$2$}$이상이어야 한다는$$ 몇 가지 증거가 있다. 가장 간단한 방법 중 하나는 크로프톤 공식을 포함하는데, 이 공식에 따르면 곡선의 길이는 선의 적절한 확률 분포로부터 무작위 선이 있는 예상 교차점 수에 비례한다. 엄격히 볼록한 슈퍼셋에$$ $의해{\displaystyle }$ K ${\displaystyle K}$에 근사하게 접근하여 문제를 단순화하면 편리하며, 원래 세트와 임의로 근접한 둘레를 선택할 수 있다. $그런{\displaystyle }$ 다음 $K{\displaystyle }$ ${\displaystyle K}($모든 선의 소멸 부분을 형성하는)에 대한 접선선을 제외하고 K ${\displaystyle$ K$}$을 교차하는 선이 경계를 두 번 교차한다$$. 따라서 무작위 선이 $확률{\displaystyle }$ p ${\displaystyle p}$과 K$${\$displaystyle K}$을$($를) 교차할 경우 예상되는 경계 교차 수는 ${\displaystyle \mathrm{2p}}$ ${\displaystyle 2p}$이다$.$ 그러나 $K{\displaystyle }$ ${\displaystyle K}$을 교차하는 각 선은 불투명 집합과 교차하므로$$, 불투명한 집합과의 예상 교차 수는 최소한이다.${\displaystyle x}$ ${\displaystyle x$ $K{\displaystyle }$ ${\displaystyle K}$에 대한 최소 절반$.$ 크로프톤 공식에 따르면 경계와 장벽의 길이는 이러한 예상 숫자와 동일한 비율을 갖는다.^[6]

매우 긴 얇은 직사각형의 경우, 하나의 긴 면과 두 개의 짧은 면이 장벽을 형성하며, 총 길이는 임의로 둘레의 절반에 가깝게 만들 수 있다. 따라서 커버리지 영역의 둘레만 고려하는 하한 중에서${\displaystyle \mathrm{}}$among ${\displaystyle K}$/ ${\displaystyle 2\mathrm{}}$ $[\디스플레이$ 스타일 $\partial K /2}$의 경계는 가장$$ 잘 가능하다.^[6] 그러나 이 경계는 달성할 수 없다. 삼각형이 아닌 모든$$ 볼록 $세트{\displaystyle }$ K$${\$displaystyle K}$에 대해 모든 불투명 세트의 길이가 최소한${\displaystyle \mathrm{}\Delta }$K /${\displaystyle 2\mathrm{}}$ + ${\displaystyle \Delta }${\$displaystyle \delta }$인 $\Delta {\displaystyle }$ ${\$$displaystyle \partial$K /$2+\delta$}이 있다$.$^[7]

특정 모양

볼록 폴리곤과 마찬가지로 삼각형의 경우, 가장 짧게 연결된 불투명 세트는 최소 스타이너 트리다.^[8] 삼각형의 경우 이 트리를 명시적으로 설명할 수 ${\displaystyle \mathrm{있다}}$: 삼각형의 가장 넓은 각도가 2${\displaystyle 2\pi /3}($120°)인 경우 또는, 그것은 삼각형의 가장 짧은 두 개의 가장자리를 사용하며, 그렇지 않으면 그것은 정점에서 삼각형의 페르마트 지점까지의 세 개의 선 세그먼트로 구성된다.^[9] 그러나, 연결을 가정하지 않고, Steiner 트리의 최적성은 증명되지 않았다. 이즈미는 정삼각형의 둘레-홀딩 하한선을 약간 개선했음을 증명했다.^[10]

For a unit square, the perimeter is 4, the perimeter minus the longest edge is 3, and the length of the minimum Steiner tree is ${\displaystyle 1+{\sqrt {3}}\approx 2.732}$. However, a shorter, disconnected opaque forest is known, with length ${\displaystyle {\sqrt {2}}+{\tfrac {1}{2}}{\s$$qrt{6}}\$약$2.639$ 네 번째 꼭지점과 중앙을 연결하는 선 세그먼트와 함께 사각형의 정점 3개의 최소 슈타이너 트리로 구성된다. 로스 혼스버거는 이 발견을 캐나다 학교 교사인 모리스 푸아리에에게 맡겼지만,^[11] 이미 1962년과 1964년에 존스에 의해 기술되었다.^[12][13] 두 가지 성분만 있는 숲 중에서 최적의 것으로 알려져 있으며,^[5][14] 일반적으로는 가장 좋은 것으로 추측되어 왔으나, 이는 입증되지 않은 채로 남아 있다.^[7] 이미 존스에 의해 입증된 사각형의 경계선 2 하한은 2.00002로 약간 개선될 수 있으며,^[12][13][7] 최대 계산 가능한 많은 수정 가능한 곡선으로 구성된 모든 장애물에 대해, 주어진 사각형 근처에만 장애물을 배치하도록 제약했던 유사한 이전 경계를 개선할 수 있다.^[6]

단위 원의 사례는 1995년 Ian Stewart의 Scientific American 칼럼에서 설명되었는데$,$^[15] 길이 $2{\displaystyle \mathrm{}}$+ ${\displaystyle \pi }$ ${\displaystyle$ 2$+\pi }$의 솔루션으로, 단일 곡선이나 연결된^[8][16][17] 장벽에는 최적이지만 다중 곡선을 가진 불투명한 숲에는 적합하지 않다. 밴스 파버와 얀 미실스키는 이 단곡선 해결책을 M에게 맡긴다. 1974년 ^[8]마기도르 1980년까지 E. Makai는 이미 길이가 약 4.7998인 더 나은 3개 구성요소 솔루션을 제공했으며,^[18] 스튜어트의 칼럼 후속으로 존 데이가 재발견했다.^[19] 최적 용액의 알 수 없는 길이를 빔 검출 상수라고 한다.^[20]

알고리즘

두 개의 공개된 알고리즘은 최적의 솔루션이 특수 구조를 가지고 있다는 생각에 근거하여 임의의 다각형에 대해 최적의 불투명 포리스트를 생성한다고 주장하는데, 폴리곤의 삼각측량에서 하나의 삼각형을 위한 Steiner 트리, 그리고 3각형의 높이와 동일한 길이의 각 정점에서 반대쪽으로 남은 각 삼각형의 세그먼트.이 구조물은 정사각형의 최적 용액의 추측 구조와 일치한다. 이 형태의 솔루션에 대한 최적 삼각측량은 이러한 알고리즘에 대한 입력의 일부가 아니지만 동적 프로그래밍을 사용하는 다항 시간대의 알고리즘에 의해 찾을 수 있다.^[21][22] 그러나 일부 폴리곤은 발견한 것과 다른 구조로 짧은 해답을 가지고 있기 때문에 이러한 알고리즘이 모든 폴리곤에 대해 문제를 정확하게 해결하지는 못한다. 특히 길고 얇은 직사각형의 경우, 4개의 꼭지점 모두의 최소 슈타이너 트리는 이러한 알고리즘이 찾는 삼각측량 기반 솔루션보다 짧다.^[23] 문제의 실행 시간과 관계없이 문제의 정확한 해결책을 찾을 수 있는 알려진 알고리즘은 없다.^[3]

이러한 차질에도 불구하고, 정점의 이동 판매원 경로인 볼록 폴리곤의 가장 짧은 단일 곡선 장벽은 동적 프로그래밍 알고리즘에 의해 볼록 폴리곤의 다항 시간에서 정확히 계산할 수 있으며, 래디컬 합계가 정확하게 계산될 수 있는 연산 모델에서 계산될 수 있다.^[4] 또한 문제에 대한 근사 알고리즘과 주어진 장벽의 적용 범위를 결정하기 위한 더 성공적인 연구가 있었다.

근사치

둘레 측면에서 불투명한 숲 길이에 대한 일반적 경계로 볼록 집합의 둘레는 길이가 2인자 이내로 가장 짧은 불투명 숲에 가깝다. 두 개의 논문에서 두미트레스쿠, 장, 파흐 및 토스는 볼록 폴리곤에 대한 가장 짧은 불투명 집합에 대해 몇 개의 선형 시간 근사 알고리즘을 제공하며, 근사비는 다음 두 개보다 높다.

• 일반 불투명 세트의 경우 근사비가 최대값인 알고리즘을 제공한다.
  $${\displaystyle {\frac {1}{1}:{2}}: {2+{\sqrt{2}}:{\pi }}}\약 1.5868.}$$

  
  알고리즘의 일반적인 개념은 입력의 최소 1미터 경계 상자에서 장벽과 같은 "보우 및 화살표"를 구성하는 것으로, 경계 상자의 한쪽 구석에서 반대쪽 구석으로 폴리곤 주위에 늘어선 다각형으로 구성되며, 경계 상자의 세 번째 모서리와 대각선을 연결하는 선 세그먼트로 구성된다. 그 ^[4]상자
• 단일 호로 구성된 불투명 세트의 경우, 근사비가 최대값인 알고리즘을 제공한다.
  $${\displaystyle {\frac {\pi +5}{\pi +2}}\약 1.5835.}$$

  
  결과 장벽은 입력 형상의 지지선에 의해 정의된다. 입력은 이 선의 간격에 수직으로 투영되며, 장벽은 원을 위한 최적의 연결 장벽처럼 입력 주위에 팽팽하게 늘어선 U자형 곡선에 의해 이 간격의 두 끝점을 연결한다. 알고리즘은 회전 캘리퍼를 사용하여 결과 장벽의 길이가 최소화되는 지지선을 찾는다.^[4]
• 연결된 불투명 세트의 경우 근사비가 $최대{\displaystyle \mathrm{}}$1.${\displaystyle 5716}$ ${\displaystyle 1.5716}$인 알고리즘을 제공한다$.$ 이 방법은 단아크 장벽과 정삼각형에 가까운 모양에 대한 특별 처리를 결합한 것으로, 삼각형의 슈타이너 트리는 더 짧은 연결 장벽이다.^[4]
• 내부 장벽의 경우 근사율이 최대 1.7168인 알고리즘을 제공한다.^[24] 아이디어는 잘못된 초기 알고리즘의 구조에 대해 셰머가 제안한 일반화(남은 입력의 삼각측정에 대한 높이 세그먼트와 함께 지점의 하위 집합에 있는 스타이너 트리)^[23]를 근사치의 스타이너 트리 부분에 대해 빠른 근사치로 사용하는 것이다.^[24]

또한 볼록 폴리곤의 가장 짧은 내부 장벽은 최소 Steiner 트리에 의해 주어지기 때문에 다항 시간 근사 체계를 가지고 있다.^[4]

커버리지

주어진 숲이 적용되는 지역은 다음과 같이 결정할 수 있다.

• 숲의 연결된 각 구성 요소의 볼록한 선체를 찾으십시오.
• 선체의 각$$ 꼭지점 $p{\displaystyle }$ ${\displaystyle p}$에 대해 $p{\displaystyle }$ ${\displaystyle p}$ 주위에 선을 원을 그리며$,$ 스위프 선이 장애물 없이 평면을 가로지르는 선체와 웨지 중 하나를 통과하는 웨지로 평면을 세분한다. 덮개가 있는 웨지의 조합은 ${\displaystyle {세트}_{}}$ C p ${\$p}}를 형성한다$.$
• 모든 세트 $C{\displaystyle {}_{}}$ ${\displaystyle p_{}}$ ${\$의 교차점을 찾으십시오$.$ 이 교차로에는 숲이 깔려 있다.

입력이 $m{\displaystyle }$ ${\displaystyle m}$ 연결$$ 구성요소를 구성하는 $n{\displaystyle }$ ${\displaystyle n}$ 선 세그먼트로$$ 구성된 경우, 각 $n{\displaystyle }$ ${\displaystyle n}$은 최대 ${\displaystyle \mathrm{2m}}$ ${\displaystyle$ $C_{$$p}$ 웨지로$$ 구성된다$$. 이어서 커버리지 영역의 결합 복잡성, 그리고 그것을 구성하는 시간은 빅 O 표기법으로 표현된$$ $O{\displaystyle }$( ${\displaystyle {}^{}}$ ${\displaystyle {2n\mathrm{}}^{}}$ 2 ) $displaystyle$O(^[25]$m^{$2}$n^{$2}n^{2}}}}이다$.$

적용 영역이 이 경계와 일치하는 결합 복잡성을 갖는 최악의 경우 최적이지만, 이 알고리즘은 $O{\displaystyle (n}$ ${\displaystyle {\log }^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}n}$) ${\displaystyle O(n\log ^{2}n)}$ 시간 내에 중복되는 선체 쌍을 병합하는 사전 처리 단계에 의해 실제로 경험적으로 경험적으로 개선될 수 있다$.$이렇게 하면 단일 선체에 대한 입력을 줄일수록 더 비싼 쓸고 교차하는 알고리즘을 실행할 필요가 없다. 이 경우 선체는 커버리지 영역이다.^[26]

곡선이 없는 불투명 세트

Mazurkiewicz(1916년)는 불투명한 집합이 비경쟁적 곡선을 포함하지 않고 총 길이가 유한하다는 것을 보여주었다.^[1] 그림에서 볼 수 있는 베이그미흘(1959년)의 단순화된 시공은 단위 사각형에 대한 예를 제시한다. 시공은 음의 기울기가 음의 모든 기울기를 차단하는 반면 양의 기울기는 모든 비 양의 기울기를 차단하는 불투명한 세트의 선 세그먼트에서 시작한다. 그림에서 이 특성을 가진 초기 세그먼트는 사각형의 대각선을 따라 4개의 분리 세그먼트다. 그런 다음 이 속성을 유지하면서 반복적으로 이러한 세그먼트를 세분화한다. 시공의 각 단계에서 각 라인 세그먼트는 중간점 근처의 작은 간격에 의해 두 라인 세그먼트로 분할되며, 동일한 부호의 기울기가 함께 원래 라인 세그먼트에 의해 차단된 반대 기호의 모든 라인을 차단한다. 이 건축물의 한계 세트는 모든 중간 단계와 마찬가지로 광장에 대한 불투명 세트인 칸토어 공간이다. 갭 크기가 빠르게 감소하면서 이 공사는 하우스도르프 치수가 하나이고, 1차원 하우스도르프 측정치(이러한 세트에 적합한 길이의 개념)가 유한한 세트를 생산한다.^[2]

정사각형의 경계 또는 정사각형에 대해 알려진 4개 세그먼트 최단 불투명 세트의 거리 집합은 둘 다 0에서 $2$까지의 간격의 모든 거리를 포함한다$.$ ${\$ 그러나 유사한 프랙탈 구조를 사용함으로써, 거리 집합이 무한히 많은 t를 생략하는 프랙탈 불투명 세트도 찾을 수 있다.그는 이 간격에서의 거리 또는 (연속 가설의) 측정값 0의 집합을 형성하는 거리.^[2]

역사

불투명 세트는 1916년에 Stefan Mazurkiewicz에 의해 원래 연구되었다.^[1] 불투명한 세트에 관한 다른 초기 작품으로는 1955년 H. M. 센 굽타와 ^[27]N. C. 바수 마줌다르의 논문과 1959년 프레데릭 베이그미흘의 논문 등이 있으나 이것들은 주로 그 길이를 최소화하기보다는 장벽의 거리 세트와 위상적 특성에 관한 것이다.^[2] 그의 논문에 대한 후기에서, 베이그미흘은 광장에 대한 내부 장벽의 최소 길이를 요구했고,^[2] 이후 작업은 주로 길이 최소화와 관련된 문제의 버전에 초점을 맞추었다. 그것들은 여러 가지 다채로운 공식으로 반복되어져 왔는데, 그것은 직립 매립 전화선을 찾기 위해 가능한 한 짧은 길이의 참호를 파거나, 숲에서 길을 잃었을 때 가까운 직선 도로를 찾으려 하고, 바다에서 길을 잃었을 때 직선 해안선까지 헤엄쳐 가고,^[8] 유리 집에 벽을 칠하는 ^[28]것 등이다.

이 문제는 또한 리만 다지관의 모든 지오디컬을 차단하는 설정이나,^[29][30] 고차원적인 설정에서 차단하는 설정으로도 일반화되었다. 3차원에서 해당 질문은 고체의 모든 가시성을 차단하는 최소 총 면적 표면의 모음을 요구한다. 그러나 공과 같은 일부 고형물의 경우, 그러한 수집품이 존재하는지 또는 그 대신 그 영역에 달성할 수 없는 최소값이 있는지 여부는 명확하지 않다.^[8][31]

참고 항목

• 벨만은 숲 문제로 길을 잃었다.
• 유클리드 과수원

참조