A decision procedure for optimal polyhedron partitioning

DOI10.1016/0020-0190(83)90028-5MaRDI QIDQ794166zbMATH OpenOpenAlexFDO

Authors Bernard Chazelle

Publication date 1983

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

Full work available at URL https://doi.org/10.1016/0020-0190(83)90028-5

zbMATH Keywords

computational geometryconvex polyhedron partitioningdecidability

Mathematics Subject Classification ID

Polytopes and polyhedra (52Bxx) Analysis of algorithms and problem complexity (68Q25)

Review text

The paper addresses the problem of subdividing a polyhedron into the smallest set of non-overlapping convex polyhedra. It is proved that the problem is decidable. (No algorithm is given, however, for the partitioning.)

Recommendations

• Computing optimal diameter-bounded polygon partitions
• Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
• A fixed parameter algorithm for optimal convex partitions
• Optimal separable partitioning in the plane
• A computational approach to an optimal partition problem on surfaces
• scientific article; zbMATH DE number 1159075
• Approximation schemes for partitioning: convex decomposition and surface approximation
• scientific article; zbMATH DE number 1538871
• scientific article; zbMATH DE number 177549
• Algorithms for fair partitioning of convex polygons

Cites work

• A new decision method for elementary algebra
• Decision procedures for real and p‐adic fields
• scientific article; zbMATH DE number 3767037 (Why is no real title available?)
• scientific article; zbMATH DE number 3261280 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• Some NP-hard polygon decomposition problems
• Triangulating a simple polygon

Cited in

(4)

• Computing optimal diameter-bounded polygon partitions
• Making Decisions in Multi Partitioning
• Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
• Stability of the 8-tetrahedra shortest-interior-edge partitioning method

This page was built for publication: A decision procedure for optimal polyhedron partitioning

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