Almost optimal polyhedral separators
Hervé Brönnimann · 1994
We animate two deterministic polynomial time methods for finding a separator for two nested convex polyhedra in 3d. While this problem is NP-complete, we show a reduction to set cover. We then animate the greedy method and the weighted method.