文章基本信息

标题：Partially Walking a Polygon
本地全文：下载
作者：Franz Aurenhammer ; Michael Steinkogler ; Rolf Klein 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：123
页码：1-9
DOI：10.4230/LIPIcs.ISAAC.2018.60
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Deciding two-guard walkability of an n-sided polygon is a well-understood problem. We study the following more general question: How far can two guards reach from a given source vertex while staying mutually visible, in the (more realistic) case that the polygon is not entirely walkable? There can be Theta(n) such maximal walks, and we show how to find all of them in O(n log n) time.
关键词：Polygon; guard walk; visibility