오목 다각형을 덮는 어떤 알고리즘은이 두 가지 방법으로 접근 할 수있는 볼록 다각형

Question

함께 (공 포함) 있는가 이러한 노조 해당 볼록 다각형을 사용하여 주어진 다각형을 피복하여 볼록 다각형

II)는 원래의 다각형을 준다. 이 경우에는 볼록 다각형 사이에 겹침이있을 수 있습니다.

분할은 전체 다각형을 다루지 만 볼록 다각형의 수는 두 번째 방법으로 줄일 수 있습니다. 볼록 다각형의 수가 최소한 인 오목한 다각형 (두 번째 접근법)을 덮는 것은 NP-Hard라는 것도 알려져 있습니다. 내가 특별히 두 번째 방법에 따라 알고리즘을 찾고 있어요

위에서 언급하지만, 볼록 다각형의 수는 최소화 될 수 없습니다. 이미 질문에 대한 코멘트에 MBO과 이브 다어 스트 언급

Answer 1

으로. 볼록 다각형으로의 다각형 분해는 삼각형 분할 (또는 사다리꼴 분해)로 수행 할 수 있습니다. 이는 n-2 (내부) 삼각형을 갖는 n 개의 꼭지점 단순 다각형 P에 대해 발생하며, 즉, 정점의 수는 선형이다.

다른 방법

볼록 분해 일반화 motorcycle graph를 사용하는 것이 구축 하였다. 나는 더 간단한 방법이 있어야한다고 생각할 것이다! 주요 아이디어는 P의 모든 반사 꼭지점 r에 대해 오토바이 m을 시작하는 것입니다. 모든 오토바이 m은 주어진 속도로 주어진 속도로 주행하고 추적을 남깁니다. 다른 오토바이가 그러한 궤적을 만나는 경우, 충돌, 즉 정지하지만 추적을 벗어납니다. 일반화는 P에 포함 된 것을 의미하며 폴리곤 경계는 오토바이가 충돌하는 벽으로 기능합니다. 또한 두 개의 오토바이가 같은 지점에서 만나는 경우 다른 차량을 시동해야합니다.이 경우에는 하나만 주행하고 다른 차량은 멈추십시오. 모든 오토바이가 추락 한 후에 실제로 P의 볼록 테셀레이션 인 자취의 그래프가 있습니다. 여기에는 몇 가지 서류 ( one here)가 있지만 구현이 어려울 것입니다. 이 O (R) 결과

P.

의 내부를 포함 볼록 다각형은 내가 가장 쉬운 방법은 삼각 측량 또는 사다리꼴 분해로 이동하는 것입니다 생각합니다. 이것들은 잘 연구되고 많은 라이브러리에서 구현할 수 있습니다.

주석에 언급 된 내용 : O (n) 다각형을 강제로 입력 할 수 있습니다. n/2 반사 정점 (내각> pi)을 갖는 별 모양의 다각형을 생각하면됩니다.