shaviava's blog

Spanning tree on grid with minimum number of turns
By shaviava, history, 6 years ago, In English

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.

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I think the spanning tree like one that on the right is always optimal

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shaviava (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

approximation algorith: first make vertical, after that horizontal edges and merge with dsu just like kruskal's.

→ Reply
»
6 years ago, # |
← Rev. 9   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply