Point Guards and Point Clouds: Solving General Art Gallery Problems

영상

Point Guards and Point Clouds: Solving General Art Gallery Problems

저작권

게시자

크레딧

Presented by the 22nd Annual Video and Multimedia Review of Computational Geometry.
Dorit Borrmann
Pedro J. de Rezende
Cid C. de Souza
Sándor P. Fekete
Stephan Friedrichs
Alexander Kröller
Andreas Nüchter
Christiane Schmidt
Davi C. Tozoni

“미술관 문제”는 계산기하(computational geometry)의 고전적인 문제입니다. 미술관(다각형)이 주어졌을 때, 몇 명의 움직이지 않는 경호원이 필요한가요? 우리는 이 문제의 실용적인 응용과 해법을 보여주겠습니다.

이 영상에서, 우리는 계산기하의 고전적 영역 중 하나가 새 흥미로운 기하 문제들을 만들게 된 실용성을 갖게 되었는지를 설명하겠습니다. 특히 우리는 플랫폼 로봇 IRMA3D가 고해상도의 삼차원 가상공간을 제한된 횟수의 레이저 스캔을 통해 만드는 과정을 보여드리겠습니다. 최적의 스캔 조합을 찾는 것은 미술관 문제(Art Gallery Problem), 즉 다각형 영역 P의 모든 점들을 지켜볼 수 있는 최소의 경비원 수를 찾는 문제를 푸는 것과 동일합니다.

이 영상은 로봇이 도시 광경을 스캔하는 것으로 시작하고, 이는 곧 설명할 미술관 문제와 관련이 있습니다. 곧이어 가시 영역(visibility polgyon)의 위치 배열에 기반해 가능한 경비와 관찰자의 위치를 분석하여, 경비들의 위치를 일반적으로 정하는 정수계획(integer programming, IP) 접근법이 소개됩니다. 이는 선형계획(linear programming, LP) 접근법으로 이어지고, 절단평면법(method of cutting planes)을 이용하여 분수계수 꼭지점들을 제거해 주는 기법이 추가됩니다. 도입부에 나온 도시의 예에 이 기법을 적용하는 것을 살펴봅니다. 마지막으로, 이렇게 구성된 스캔들은 합쳐져서 도시환경의 가상의 풍경을 가시광선과 자외선으로 보여줍니다.

이 비디오는 29회 계산기하 심포지엄(Annual Symposium on Computational Geometry)에 있었던 22회 계산기하 비디오/멀티미디어 회고(Annual Video and Multimedia Review of Computational Geometry)에 속합니다.

관련 자료

영상 더 보기