论文标题
美术馆问题的拓扑普遍性
Topological Universality of the Art Gallery Problem
论文作者
论文摘要
我们证明，任何紧凑的半代数套件都是对某些美术馆问题的解决方案空间的同构。以前的作品已经建立了类似的普遍性定理，但仅符合同质术等效而不是同态性，并且在这项工作之前，即使在诸如Möbius条或三孔的圆环之类的简单空间中，艺术画廊的存在也是未知的。我们的建筑依靠一个优雅而多功能的小工具来复制以最少的头顶来复制警卫位置。它比以前的结构简单，由一个矩形房间组成，其边缘切出凸槽。我们表明，只有$ o（n）$顶点的属属$ n $ en $ n $ n $ n $ n $ n $ n $ contrface的表面。
We prove that any compact semi-algebraic set is homeomorphic to the solution space of some art gallery problem. Previous works have established similar universality theorems, but holding only up to homotopy equivalence, rather than homeomorphism, and prior to this work, the existence of art galleries even for simple spaces such as the Möbius strip or the three-holed torus were unknown. Our construction relies on an elegant and versatile gadget to copy guard positions with minimal overhead. It is simpler than previous constructions, consisting of a single rectangular room with convex slits cut out from the edges. We show that both the orientable and non-orientable surfaces of genus $n$ admit galleries with only $O(n)$ vertices.
