On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees

DOI10.1016/S0925-7721(97)00006-0zbMath0881.68121OpenAlexW2010348345MaRDI QIDQ1367169

Michael T. Goodrich, Gautam K. Das

Publication date: 9 November 1997

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0925-7721(97)00006-0

zbMATH Keywords

decision trees3-dimensional convex polyhedra

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Embedding stacked polytopes on a polynomial-size grid ⋮ Skyscraper polytopes and realizations of plane triangulations ⋮ Realizing Planar Graphs as Convex Polytopes ⋮ Computing cup products in \(\mathbb{Z}_2\)-cohomology of 3D polyhedral complexes ⋮ Small grid embeddings of 3-polytopes ⋮ Extending Steinitz's theorem to upward star-shaped polyhedra and spherical polyhedra ⋮ Sparse convex hull coverage ⋮ Cup Products on Polyhedral Approximations of 3D Digital Images ⋮ A geometric lower bound on the extension complexity of polytopes based on the \(f\)-vector ⋮ Computational complexity of the vertex cover problem in the class of planar triangulations ⋮ A duality transform for constructing small grid embeddings of 3d polytopes ⋮ SEPARABILITY OF POINT SETS BY k-LEVEL LINEAR CLASSIFICATION TREES ⋮ On the geometric interpretation of the nonnegative rank ⋮ Polyhedral approximation and practical convex hull algorithm for certain classes of voxel sets ⋮ Advances in the theory and practice of graph drawing

Uses Software

• C4.5

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast detection of polyhedral intersection
• Minimum polygonal separation
• On the complexity of loading shallow neural networks
• On the complexity of polyhedral separability
• Minimum vertex hulls for polyhedral domains
• Constructing optimal binary decision trees is NP-complete
• Some simplified NP-complete graph problems
• Finding minimal convex nested polygons
• Congruence, similarity, and symmetries of geometric objects
• Almost optimal set covers in finite VC-dimension
• Finding the smallest triangles containing a given convex polygon
• Optimal Search in Planar Subdivisions
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• An Efficient Simplex Coverability Algorithm in E2 with Application to Stochastic Sequential Machines
• Algorithms for polytope covering and approximation