Find optimal room from which to visit all other rooms in a rectangular floorplan Suppose we have an orthogonal polygon with holes (all walls are axis-parallel).  All vertices can be on integer coordinates, if that helps.  Partition the polygon into rectangular rooms.  I would like to find the best room to start from, to visit all the rooms (rectangles). There's a limitation on my movement: in any room, I can only leave by two directions, say north and west. (Here best means there would only be one source in the plane dual graph with directed edges showing how to walk from room to room. If more than one source is required, I wish to minimize them.) 

I have been looking at art gallery problems, and at VLSI papers on building rectilinear floorplans from network flows, and they are all tantalizingly close but far.  Can anyone provide suggestions so I can focus my search/proof construction?

EDIT to fix problem pointed out by Peter Taylor.  I can choose two directions per room. (probably they need to be adjacent, so NE is ok but NS is not.)  If I enter one room northward, I am automatically choosing South as one of thst new room's directions. (so only two in or out directions per room)  If I choose a  direction, and there are multiple rooms adjacent in that direction, I can enter all of them (and all of them then have the reverse direction assigned as one of their two directions), so the naive greedy approach would be to choose the direction that maximizes the number of rooms I can enter at that stage. I hope this is now complete, and understandable.
(This is joint with Jeff Phillips, who refuses to visit cstheory regularly ;))
I'm working with the problem formulation as stated and evolved in the comments. Namely, the goal is to find a minimum number of &quot;robots&quot; who can traverse a partition of an orthogonal polygon into rectangles, with the constraint that:

A room can be entered and exited only in diametrically opposed directions (so north-south OR east-west)
A robot can only cross room boundaries along one (globally chosen) axis (so no 90 degree turns allowed)
Within a room though, a robot can do whatever it likes, as long it crosses room boundaries as specified.
Robots can backtrack arbitrarily as long as they follow the above rules.

So a solution looks like an assignment of &quot;colors&quot; axes (NS or EW) to each room, and a traversal plan where each robot only traverses rooms having the same &quot;color&quot;.
Construct a graph where each rectangle is a vertex and two rectangles are marked as adjacent if they share a boundary. The edge is &quot;colored&quot; NS or EW, depending on the nature of the adjacency.
Claim 1: If we are limited to one axis (NS or EW) then the minimum number of robots is merely the number of components in graph induced by edges of the corresponding color.
Proof: Every edge represents a legal transition in that axis, so placing one robot in each connected component suffices, and you need at least one for each component for coverage.
Now consider the two partitions of the rectangle collection induced by the two colors. Notice that the minimum cardinality partition among these two might be far from optimal if for example your polygon is an L shape with each leg subdivided into n/2 rectangles. The individual graphs each have n/2 components, but the optimal solution is of size 2.
Construct a bipartite graph, in each node is one of the connected components of either of the partitions, and two nodes are connected if their corresponding components intersect. This graph is bipartite because the two sets of components were partitions.
Claim: the size of minimum vertex cover in this graph is the desired optimal soln.
Proof.
Firstly note that in any optimal solution, the set of rectangles covered by any robot must be a subset of one of the components by reachability. Further, it costs nothing for this robot to cover any of the other rectangles in this partition. Hence wlog we can assume that OPT consists of a set of components that together cover all rectangles, i.e a set cover.
Secondly, since the graph is bipartite, we know that any rectangle is represented by exactly one edge between left and right sides. Thus, covering all rectangles actually requires covering all edges in this graph.
QED
VC in bipartite graphs can be solved in polynomial time, so the overall problem can be solved in polynomial time.
Comments ?