Cutting a Convex Polyhedron Out of a Sphere

2009/07/23 by Syed Ishtiaque Ahmed, Ahmed, Syed Ishtiaque, Masud Hasan +3
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.0907.4068

openalex publication_date 2009/07/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a convex polyhedron P of n vertices inside a sphere Q, we give an O(n³)-time algorithm that cuts P out of Q by using guillotine cuts and has cutting cost O((log n)²) times the optimal.

Related

• Convex Polygon Containment: Improving Quadratic to Near Linear Time
• A Fast Algorithm for Line Clipping by Convex Polyhedron in E3
• Unfolding Convex Polyhedra via Radially Monotone Cut Trees
• Optimally cutting a surface into a disk
• PolyChopper: a Polyhedron Splitting Scheme