Next: Sets and Partitions Up: Miscellaneous Previous: MINIMUM LENGTH TRIANGULATION Index

### MINIMUM SEPARATING SUBDIVISION

- INSTANCE: A family of disjoint polygons .

- SOLUTION: A separating subdivision, i.e., a family of k polygons with pairwise disjoint boundaries such that, for each i, .

- MEASURE: The size of the subdivision, i.e., the total number of edges of the polygons .

- Good News: Approximable within 7 [358].

- 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.