Finding the Straight Skeleton for 3D Orthogonal Polyhedrons: A Combinatorial Approach

A combinatorial algorithm is presented here to determine the straight skeleton of a given 3D orthogonal polyhedron in \(O(n\log n)\) time, where n is the number of vertices in the 3D orthogonal polyhedron. The 3D orthogonal polyhedron is traversed by considering a cuboid at each step. One of the combinatorial rule is applied and a part of the 3D orthogonal polyhedron is discarded as per the reduction rule. When the whole 3D polyhedron is traversed, the straight skeleton is obtained. The straight skeleton has many applications in shape analysis, shape matching, and shape retrieval.