Testing surface area with arbitrary accuracy

Abstract: Recently, Kothari et al. gave an algorithm for testing the surface area of an arbitrary set

A s u b s e t [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

k a p p a_{n} S

. Here,

k a p p a_{n}

is a dimension-dependent constant which is strictly larger than 1 if

n g e 2

, and grows to

4 / p i

as

n o i n f t y

. We give an improved analysis of Kothari et al.'s algorithm. In doing so, we replace the constant

k a p p a_{n}

with

1 + e t a

for

e t a > 0

arbitrary. We also extend the algorithm to more general measures on Riemannian manifolds.

Cites Work

Cited In (5)

Uses Software

This page was built for publication: Testing surface area with arbitrary accuracy