Suppose youre a consultant for the Ergonomic Architecture Commission, and they come to you with the following problem.

Theyre really concerned about designing houses that are user- friendly, and theyve been having a lot of trouble with the setup of light fixtures and switches in newly designed houses. Consider, for example, a one-floor house with n light fixtures and n locations for light switches mounted in the wall. Youd like to be able to wire up one switch to control each light fixture, in such a way that a person at the switch can see the light fixture being controlled.

Sometimes this is possible and sometimes it isnt. Consider the two simple floor plans for houses in Figure 7.28. There are three light fixtures (labeled a, b, c) and three switches (labeled 1, 2, 3). It is possible to wire switches to fixtures in Figure 7.28(a) so that every switch has a line of sight to the fixture, but this is not possible in Figure 7.28(b).

Lets call a floor plan, together with n light fixture locations and n switch locations, ergonomic if its possible to wire one switch to each fixture so that every fixture is visible from the switch that controls it. A floor plan will be represented by a set of m horizontal or vertical line segments in the plane (the walls), where the ith wall has endpoints (xi , yi), (xi , yi). Each of the n switches and each of the n fixtures is given by its coordinates in the plane. A fixture is visible from a switch if the line segment joining them does not cross any of the walls.

Give an algorithm to decide if a given floor plan is ergonomic. The running time should be polynomial inm and n. You may assume that you have a subroutine with O(1) running time that takes two line segments as input and decides whether or not they cross in the plane. Also, provide the time complexity of your algorithm.

(If it's not too much to ask, proof of correctness for the algorithm too, please!)

DID 2 3 (b) Not ergonomic (a) Ergonomic Figure 7.28 The floor plan in (a) is ergonomic, because we can wire switches to fixtures in such a way that each fixture is visible from the switch that controls it. (This can be done by wiring switch 1 to a, switch 2 to b, and switch 3 to c. The floor plan in (b) is not ergonomic, because no such wiring is possible