Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MINIMUM SEPARATING SUBDIVISION

• INSTANCE: A family of disjoint polygons $P_1, \ldots, P_k$.

• SOLUTION: A separating subdivision, i.e., a family of k polygons $R_1, \ldots, R_k$ with pairwise disjoint boundaries such that, for each i, $P_i \subseteq R_i$.

• MEASURE: The size of the subdivision, i.e., the total number of edges of the polygons $R_1, \ldots, R_k$.

  
  

• Good News: Approximable within 7 [378].

• Comment: The problem of separating a family of three-dimensional convex polyhedra is approximable within $O(\log n)$ while the problem of separating two d-dimensional convex polyhedra is approximable within $O(d\log n)$ where n denotes the number of facets in the input family.