### shaviava's blog

By shaviava, history, 4 years ago,

Is there a polynomial algorithm to find a spanning tree of an undirected grid graph which minimizes the number of turns in tree? A turn is when there are two edges connected to one vertex which have perpendicular directions.

In this problem we have arbitrary set of cells in grid which form a connected graph (not only rectangles are considered). Thus, set of cells may form concave areas and areas with holes

For example, given a 4 x 4 grid graph (see image below), we want to find a spanning tree like that on the right (which has 6 turns) rather than that on the left (which has 14):

Ideas about approximate algorithms may be useful too.

• +15

 » 4 years ago, # |   +3 I think the spanning tree like one that on the right is always optimal
•  » » 4 years ago, # ^ | ← Rev. 4 →   0 But cells in the grid form not always a rectangle. For example, for Г-shaped set of cells the optimal tree is г------------------г------------------гттт--------------|||||||||||||||||||||||| H-shaped grid is more difficult
•  » » » 4 years ago, # ^ |   0
•  » » » » 4 years ago, # ^ |   0 But that's not a grid graph?
•  » » » » » 4 years ago, # ^ |   0 Subset of cells in grid?
 » 4 years ago, # |   0 Auto comment: topic has been updated by shaviava (previous revision, new revision, compare).
 » 4 years ago, # |   0 approximation algorith: first make vertical, after that horizontal edges and merge with dsu just like kruskal's.
 » 4 years ago, # | ← Rev. 9 →   0 The expanded problem of this problem has already been taken here and can be solved using the Kruskal method.There is editorial on the link.(It is considered only when it is a rectangle)　Even when it is not a rectangle, I think that it can be solved by the usual Kruskal method by setting the cost of the edge between adjacent vertices to 1.
•  » » 4 years ago, # ^ |   0 There was a simple mst, but I want to minimize numbers of turns. And I can't reformulate this problem in terms of problem from atcoder