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

DOI10.1016/0020-0190(91)90207-XzbMATH Open0732.68050OpenAlexW2027668079MaRDI QIDQ808703FDOQ808703

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

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

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)

Cites Work

• Title not available (Why is that?)
• Some NP-hard polygon decomposition problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Covering Regions by Rectangles
• Finding a manhattan path and related problems

Cited In (11)

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

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)