Next: Sets and Partitions
Up: Miscellaneous
Previous: MINIMUM LENGTH TRIANGULATION
  Index
- 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 [378].
- 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.
Viggo Kann
2000-03-20