Rectangular partition is polynomial in two dimensions but NP-complete in three

DOI10.1016/0020-0190(91)90207-XMaRDI QIDQ808703zbMATH OpenOpenAlexFDO

Authors Victor J. Dielissen, Anne Kaldewaij

Publication date 1991

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(91)90207-x

zbMATH Keywords

NP-completepolygon decomposition

Mathematics Subject Classification ID

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

Recommendations

• Partitioning a square into rectangles: NP-Completeness and approximation algorithms
• scientific article; zbMATH DE number 4049401
• Partitioning a planar assembly into two connected parts is NP-complete
• The polynomial dichotomy for three nonempty part sandwich problems
• The polynomial dichotomy for three nonempty part sandwich problems
• Partitioning to three matchings of given size is NP-complete for bipartite graphs
• A Polynomial Time Algorithm for Shaped Partition Problems
• Some efficiently solvable problems over integer partition polytopes
• EXACT SOLUTIONS OF RECTANGULAR PARTITIONS VIA INTEGER PROGRAMMING

Cites work

• 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 3639144 (Why is no real title available?)
• Covering Regions by Rectangles
• Finding a manhattan path and related problems
• Some NP-hard polygon decomposition problems

Cited in

(11)

• Cartesian product partitioning of multi-dimensional reachable state spaces
• 3D rectangulations and geometric matrix multiplication
• Close-to-optimal algorithm for rectangular decomposition of 3D shapes.
• 3D rectangulations and geometric matrix multiplication
• Minimum convex partition of a polygon with holes by cuts in given directions
• Minimal Decomposition of a Digital Surface into Digital Plane Segments Is NP-Hard
• Partitioning a planar assembly into two connected parts is NP-complete
• Approximation algorithms for decomposing octilinear polygons
• Minimum decomposition of a digital surface into digital plane segments is NP-hard
• PARTITIONING 3D PHANTOMS INTO HOMOGENEOUS CUBOIDS
• Formulas for the number of \((n-2)\)-gaps of binary objects in arbitrary dimension

This page was built for publication: Rectangular partition is polynomial in two dimensions but NP-complete in three

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