이 영상에서, 우리는 계산기하의 고전적 영역 중 하나가 새 흥미로운 기하 문제들을 만들게 된 실용성을 갖게 되었는지를 설명하겠습니다. 특히 우리는 플랫폼 로봇 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)에 속합니다.