Separation and approximation of polyhedral objects

Given a family of disjoint polygons P₁, P₂, ., Pκ in the plane, and an integer parameter m, it is ./VP-complete to decide if the Pi 's can be separated by a polygonal family consisting of m edges, that is, if there exist polygons R₁, R₂, ., Rκ with pairwise-disjoint boundaries such that P_i ⊆ R_i and ∑|R_i| ≤ m. In three dimensions, the problem of separating even two nested convex polyhedra by a κ-facet polyhedron is ./VP-complete. Many other extensions and generalizations of the polyhedral separation problem, either to families of polyhedra or to higher dimensions, are also intractable. In this paper, we present efficient approximation algorithms for constructing separating families of near-optimal size. Our main results are as follows. In two dimensions, we give an O(n log n) time algorithm for constructing a separating family whose size is within a constant factor of an optimal separating family; n is the number of edges in the input family of polygons. In three dimensions, we can separate a convex polyhedron from a nonconvex polyhedron with a convex polyhedral surface whose facet-complexity is O(logn) times the optimal, where n = |P|+|Q| is the complexity of the input polyhedra. Our algorithm runs in O(n⁴) time, but improves to O(n³) time if the two polyhedra are nested and convex. Our algorithm for separating a convex polyhedron from a nonconvex polyhedron extends to higher dimensions. In d dimensions, for d ≥ 4, the facet-complexity of the approximation polyhedron is O(d log n) times the optimal, and the algorithm runs in O(n^d+1) time. Finally, we also obtain results on separating sets of points, a family of convex polyhedra, and separation by non-polyhedral surfaces, such as spherical patches.