4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you restate the problem so that it's obvious why "Start in the southeast corner" isn't a trivial solution? $\endgroup$ – Peter Taylor Jan 30 '11 at 17:49
  • $\begingroup$ Can you please elaborate on your cost model? Are you talking about a static property (minimal walking distances) or a dynamic one (visit all rooms in one sweep and backtrack as little as possible)? Do you have to return to you starting room? $\endgroup$ – Raphael Jan 30 '11 at 18:38
  • $\begingroup$ @Raphael: the area of each room does not matter; nor does the distance traversed. (maybe later, yes, to tweak optimization) But for now: The only cost is the number of independent sources (starting rooms) required to visit all the rooms with the two-direction limitation. So the problem feels topological to me, not that that has helped me any. $\endgroup$ – Aaron Sterling Jan 30 '11 at 18:55
  • $\begingroup$ This week I studied a lot about robotics, so I am going ahead and propose markov decision processes. I don't believe it can solve your problem right away , but trying it on relatively small polygons can perhaps give you a clue about what consists a good strategy/policy. $\endgroup$ – chazisop Jan 30 '11 at 19:35
  • $\begingroup$ so if I understand correctly, the goal now is not to charge for distance travelled or cells visited, but to charge for number of sources needed ? $\endgroup$ – Suresh Venkat Jan 31 '11 at 17:11
1
$\begingroup$

(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 "robots" 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 "colors" axes (NS or EW) to each room, and a traversal plan where each robot only traverses rooms having the same "color".

Construct a graph where each rectangle is a vertex and two rectangles are marked as adjacent if they share a boundary. The edge is "colored" 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 ?

$\endgroup$
  • $\begingroup$ Thank you, Suresh. I think my asking of this question must have been profoundly bad, because NS and EW are prohibited, but adjacent directions are ok. This may solve an orthogonal problem though, which could be very helpful, don't know yet. In any case, I think I may have solved the case of a simple polygon anyway: it seems related to problems of rectilinear link center and link distance. Choose a point in the link center, and draw the link graph to representative points in all rectangles. Then weight vertices wih (width, height) and use dynamic programming to minimize weight traversed. $\endgroup$ – Aaron Sterling Feb 3 '11 at 18:44
  • $\begingroup$ That's sketchy, I know. I will post something more complete after the weekend, once I am more sure my idea works (or doesn't). Snow and chemoinformatics have kept me from logging in here much this week. $\endgroup$ – Aaron Sterling Feb 3 '11 at 18:48
  • $\begingroup$ ok that's confusing though, because in your post you were very clear that dimensions didn't matter: you merely wanted to count the number of robots needed. Your comment suggests that dimensions matter. $\endgroup$ – Suresh Venkat Feb 3 '11 at 19:38
0
$\begingroup$

I assume that by "best starting room" you mean that it minimizes the sum of shortest walking distances from a fixed room to all the others.

Model your floor as undirected graph. Each room is a node. Nodes are connected if and only if there is a direct physical, walkable connection between them (such as a door). You can model hallways as a series of sufficiently small rooms, such as one piece per door. If you want, you can even model actual walking distances (center nodes in their rooms) by edge weights.

Once you have done this perform a SSSP (single source shortest path) algorithm for every non-hallway node. Choose the starting node that minimises the sum of distances found to all non-hallway nodes.

Note that this solution does not account for "saving" distance when visiting several rooms in a row. Such scenarios can be solved with the same model, but would become unpleasantly close to TSP (traveling salesman), but for your input sizes things should still work out.

(I am minimising the wrong thing, aren't I?)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.