scientific article; zbMATH DE number 3883609
[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.
- Algorithms for minimum length partitions of polygons
- Improved bounds for rectangular and guillotine partitions
- Decompositions, partitions, and coverings with convex polygons and pseudo-triangles
- Approximate convex decomposition of polygons
- Rectangular partitions of a rectilinear polygon
- On d-convex partitions of polygonal regions
- Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
- Asymptotics of Perimeter-Minimizing Partitions
- scientific article; zbMATH DE number 4062592 (Why is no real title available?)
- scientific article; zbMATH DE number 1159075 (Why is no real title available?)
- Constant-factor approximation for TSP with disks
- MINIMUM NUMBER OF PIECES IN A CONVEX PARTITION OF A POLYGONAL DOMAIN
- Linear-time heuristics for minimum weight rectangulation
- Minimum weight convex Steiner partitions
- On heuristics for minimum length rectilinear partitions
- Computational Science and Its Applications – ICCSA 2004
- Observation routes and external watchman routes
- Observation routes and external watchman routes
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)