CVC Seminar Wed Sept 7 1:15-2:30pm ACES 4.304

Speaker: John Edwards

Title: Polyhedron Separation

Abstract: A polyhedron K is said to separate polyhedra P and Q if any path from any point on the surface of Q to any point on the surface of P passes through the surface of K. An optimal separating polyhedron among all K has the fewest possible facets. Finding an optimal separator in 2D can be done in O(nlogn) time. Finding an optimal separator in 3D has been shown to be NP-hard. Approximation algorithms exist, but only for convex P and Q. I will present a new algorithm that works on arbitrary P and Q and has similar performance guarantees (in terms of facet complexity) to the algorithms restricted to the convex case.