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.8779837489128113
0 references
0.8722277283668518
0 references
0.8613675236701965
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