Bounds for point recolouring in geometric graphs
详细信息 查看全文
- 作者：Henk Meijer ; Yurai Nú ; ñ ; ez-Rodrí ; guez ; David Rappaport
- 关键词：Computational geometry ; Point recolouring ; Triangulation ; Geometric graph
- 刊名：Computational Geometry
- 出版年：2009
- 出版时间：August 2009
- 年：2009
- 卷：42
- 期：6-7
- 页码：690-703
- 全文大小：1386 K
文摘
We examine a recolouring scheme ostensibly used to assist in classifying geographic data. Given a drawing of a graph with bi-chromatic points, where the points are the vertices of the graph, a point can be recoloured if it is surrounded by neighbours of the opposite colour. The notion of surrounded is defined as a contiguous subset of neighbours that span an angle greater than 180 degrees. The recolouring of surrounded points continues in sequence, in no particular order, until no point remains surrounded. We show that for some classes of graphs the process terminates in a polynomial number of steps. On the other hand, there are classes of graphs with infinite recolouring sequences.