On heuristics for minimum length rectilinear partitions

The problem of partitioning a rectilinear figure into rectangles with minimum length is NP-hard and has bounded heuristics. In this paper we study a related problem,Elimination Problem (EP), in which a rectilinear figure is partitioned into a set of rectilinear figures containing no concave vertices of a fixed direction with minimum length. We show that a heuristic for EP within a factor of 4 from optimal can be computed in timeO(n ²), wheren is the number of vertices of the input figure, and a variant of this heuristic, within a factor of 6 from optimal, can be computed in timeO(n logn). As an application, we give a bounded heuristic for the problem of partitioning a rectilinear figure into histograms of a fixed direction with minimum length.An auxiliary result is that an optimal rectangular partition of a monotonic histogram can be computed in timeO(n ²), using a known speed-up technique in dynamic programming.Part of this work was done when the first author was a postdoctor fellow in MSRI, Berkeley, and supported in part by NSF Grant No. 8120790. The second author was supported in part by NSF Grant No. DCR-8411945.