No label defined (Q3217601)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3883609
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3883609

      Statements

      1984
      0 references
      convex partitions of polygons
      0 references
      heuristic algorithms
      0 references
      partitioning rectilinear polygons into rectangles
      0 references
      0 references
      0 references
      [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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references