Separation and approximation of polyhedral objects

摘要: Given a family of disjoint polygons P1, P2,…, Pk in the plane, and an integer parameter m, it is NP-complete to decide if Pi's can be separated by polygonal consisting m edges, that is, there exist R1, R2,…, Rk with pairwise-disjoint boundaries such Pi *** Ri S|Ri| ≤ m. In three dimensions, problem separating even two nested convex polyhedra k-facet polyhedron NP-complete. Many other extensions generalizations polyhedral separation problem, either families or higher are also intractable. this paper, we present efficient approximation algorithms for constructing near-optimal size. Our main results as follows. give O(n log n) time algorithm whose size within constant factor optimal family; n number edges input polygons. separate from nonconvex surface facet-complexity O(log n, times optimal, where = |P|+|Q| complexity polyhedra. runs O(n4) time, but improves O (n3) convex. extends dimensions. d ≥ 4, O(d O(nd+1)time. Finally, obtain on sets points, polyhedra, non-polyhedral surfaces, spherical patches.