Testing surface area with arbitrary accuracy

Abstract

Recently, Kothari et al. gave an algorithm for testing the surface area of an arbitrary set A ⊂ [0,1]n. Specifically, they gave a randomized algorithm such that if A's surface area is less than S then the algorithm will accept with high probability, and if the algorithm accepts with high probability then there is some perturbation of A with surface area at most κnS. Here, κn is a dimension-dependent constant which is strictly larger than 1 if n ≥ 2, and grows to 4/π as n → ∞.