Spanning tree on grid with minimum number of turns

Revision en6, by shaviava, 2018-08-03 16:12:07

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.

#### History

Revisions

Rev. Lang. By When Δ Comment
ru3 shaviava 2018-08-05 10:11:40 2 Мелкая правка: 'о слева (14 поворотов' -> 'о слева (15 поворотов'
ru2 shaviava 2018-08-04 17:38:00 18
ru1 shaviava 2018-08-04 17:36:00 686 Первая редакция перевода на Русский
en6 shaviava 2018-08-03 16:12:07 10 Tiny change: 'Is there an algorithm' -> 'Is there a polynomial algorithm'
en5 shaviava 2018-08-03 15:56:05 64
en4 shaviava 2018-08-03 14:42:41 37 Tiny change: 'cted graph.\n\nFor e' -> 'cted graph (not only rectangles are considered).\n\nFor e'
en3 shaviava 2018-08-03 13:38:23 0 (published)
en2 shaviava 2018-08-03 13:18:57 88 (saved to drafts)
en1 shaviava 2018-08-03 13:00:47 546 Initial revision (published)