Minimum dissection of a rectilinear polygon with arbitrary holes into rectangles

DOI10.1007/BF02189307MaRDI QIDQ1196367zbMATH OpenFDO

Authors Alexei Gorpinevich, Valeriu Soltan

Publication date 14 December 1992

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/131234

zbMATH Keywords

holesrectanglesrectilinear polygons

Mathematics Subject Classification ID

Discrete geometry (52C99) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

The authors give a formula for a minimum number of dissecting rectangles for a given rectangular polygon with arbitrary (possibly, degenerate) holes. They also give a polynomial time algorithm for dissecting the polygon in a minimum number of rectangles. The holes can degenerate into points. This fact disproves an assertion about the \(NP\)-hardness of this problem.

Recommendations

• scientific article; zbMATH DE number 4049401
• Minimum k-partitioning of rectilinear polygons
• Linear-time heuristics for minimum weight rectangulation
• Performance Guarantees on a Sweep-Line Heuristic for Covering Rectilinear Polygons with Rectangles
• Minimum convex partition of a polygon with holes by cuts in given directions

Cites work

• Efficient Algorithms for Geometric Graph Search Problems
• Finding a manhattan path and related problems
• scientific article; zbMATH DE number 3700274 (Why is no real title available?)
• scientific article; zbMATH DE number 3767037 (Why is no real title available?)
• scientific article; zbMATH DE number 3598499 (Why is no real title available?)
• scientific article; zbMATH DE number 4197429 (Why is no real title available?)
• Minimal rectangular partitions of digitized blobs

Cited in

(16)

• On convex partitions of polygonal regions
• Lower bounds for approximate polygon decomposition and minimum gap
• Minimum stabbing rectangular partitions of rectilinear polygons
• Extracting compact fuzzy rules based on adaptive data approximation using B-splines
• Approximation algorithms for decomposing octilinear polygons
• Dissection with the fewest pieces is hard, even to approximate
• Effect of corner information in simultaneous placement of k rectangles and tableaux
• MINIMUM NUMBER OF PIECES IN A CONVEX PARTITION OF A POLYGONAL DOMAIN
• Cartesian product partitioning of multi-dimensional reachable state spaces
• Optimal matrix-segmentation by rectangles
• A hybrid heuristic for the rectilinear picture compression problem
• Minimum convex partition of a polygon with holes by cuts in given directions
• Orthogonal dissection into few rectangles
• Storylines with a protagonist
• Recognizing integrality of weighted rectangles partitions
• Minimum rectilinear polygons for given angle sequences

This page was built for publication: Minimum dissection of a rectilinear polygon with arbitrary holes into rectangles

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