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

DOI10.1016/0020-0190(91)90207-XzbMath0732.68050OpenAlexW2027668079MaRDI QIDQ808703

Anne Kaldewaij, Victor J. Dielissen

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)

Related Items

3D Rectangulations and Geometric Matrix Multiplication ⋮ Approximation algorithms for decomposing octilinear polygons ⋮ CARTESIAN PRODUCT PARTITIONING OF MULTI-DIMENSIONAL REACHABLE STATE SPACES ⋮ 3D rectangulations and geometric matrix multiplication ⋮ PARTITIONING 3D PHANTOMS INTO HOMOGENEOUS CUBOIDS ⋮ Formulas for the number of \((n-2)\)-gaps of binary objects in arbitrary dimension ⋮ Close-to-optimal algorithm for rectangular decomposition of 3D shapes

Cites Work

• Finding a manhattan path and related problems
• Some NP-hard polygon decomposition problems
• Covering Regions by Rectangles
• Unnamed Item
• Unnamed Item
• Unnamed Item