ND59 M INIMUM S EPARATING S UBDIVISION

     
• I NSTANCE : A family of disjoint polygons .
• S OLUTION : A separating subdivision, i.e., a family of k polygons with pairwise disjoint boundaries such that, for each i , .
• M EASURE : The size of the subdivision, i.e., the total number of edges of the polygons .

• Good News: Approximable within 7 [ 274 ].
• Comment: The problem of separating a family of three-dimensional convex polyhedra is approximable within while the problem of separating two d -dimensional convex polyhedra is approximable within where n denotes the number of facets in the input family.