A polynomial time solution for labeling a rectilinear map

Abstract

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