Approximation Algorithms for Geometric Separation Problems
Joseph S. B. Mitchell · 2009
In computer graphics and solid modeling, one is interested in representing complex geometric objects with combinatorially simpler ones. It turns out that via a "fattening" transformation, one obtains a formulation of the approximation problem in terms of separation: Find a minimumcomplexity surface that separates two sets. In this paper, we provide approximation algorithms for several geometric separation problems, including: .