scientific article; zbMATH DE number 3883609

From MaRDI portal
Publication:3217601





[For the entire collection see Zbl 0542.00016.] A heuristic for partitioning rectilinear polygons into rectangles, and polygons into convex parts by drawing lines of minimum total length is proposed. For the input polygon with n vertices, k concave vertices and the perimeter of length p, the heuristic draws partitioning lines of total length O(p log k) and runs in time O(n log n). To demonstrate that the heuristic comes close to optimal in the worst case, a uniform family of rectilinear polygons \(Q_ k\) with k concave vertices, \(k=1,2,...\) and a uniform family of polygons \(P_ k\) with k concave vertices, \(k=1,2,...\) are constructed such that any rectangular partition of \(Q_ k\) has (total line) length \(\Omega\) (p log k), and any convex partition of \(P_ k\) has length \(\Omega\) (p log k/log log k). Finally, a generalization of the heuristic for minimum length of convex partition of simple polygons to include polygons with polygonal holes is given.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3217601)