A POLYNOMIAL-TIME SOLUTION FOR LABELING A RECTILINEAR MAP

Given a rectilinear map consisting of n disjoint line segments, the co rresponding map labeling problem is to place a maximum width rectangle at each segment using one of the three natural ways. In a recent pape r, it is shown that if all segments are horizontal then the problem ca n be solved in optimal Theta(n log n) time. For the general problem a factor-2 approximate solution and a Polynomial Time Approximation Sche me are also proposed. In this paper, we show that the general problem is polynomially solvable with a nontrivial use of 2SAT and the solutio n can be even generalized to the case of allowing k natural placements for each segment, where k is any fixed constant. We believe this tech nique can be also used to solve other geometric packing problems. (C) 1998 Elsevier Science B.V.