We study unit disk visibility graphs, where the visibility relation between a pair of geometric entities is defined by not only obstacles, but also the distance between them. That is, two entities are not mutually visible if they are too far apart, regardless of having an obstacle between them. This particular graph class models real world scenarios more accurately compared to the conventional visibility graphs. We first define and classify the unit disk visibility graphs, and then show that the 3-coloring problem is NP-complete when unit disk visibility model is used for a set of line segments (which applies to a set of points) and for a polygon with holes.
翻译：我们研究单位磁盘可见度图形,其中一对几何实体之间的可见度关系不仅以障碍来界定,而且以它们之间的距离来界定。也就是说,两个实体如果相距太远,就不是相互可见的,不管它们之间有障碍。这个特定的图形级模型与传统的可见度图形相比,真实世界的情景更加准确。 我们首先定义和分类单元磁盘可见度图形,然后显示当将单元磁盘可见度模型用于一组线段(适用于一组点)和带孔的多边形时,3色问题就是NP-完整的。
相关内容
微信扫码咨询专知VIP会员