Testing Connectedness of Images

Abstract

We investigate algorithms for testing whether an image is connected. Given a proximity parameter $\hat{I}\mu \in (0,1)$ and query access to a black-and-white image represented by an $n\times n$ matrix of Boolean pixel values, a (1-sided error) connectedness tester accepts if the image is connected and rejects with probability at least 2/3 if the image is $\hat{I}\mu$-far from connected. We show that connectedness can be tested nonadaptively with $O(\frac{1}{\hat{I}{\mu }^2})$ queries and adaptively with $O(\frac{1}{\hat{I}{\mu }^{3/2}}\sqrt{\log \frac{1}{\hat{I}}\mu })$ queries. The best connectedness tester to date, by Berman, Raskhodnikova, and Yaroslavtsev (STOC 2014) had query complexity $O(\frac{1}{\hat{I}{\mu }^2}\log \frac{1}{\hat{I}}\mu )$ and was adaptive. We also prove that every nonadaptive, 1-sided error tester for connectedness must make $\hat{I}\text{c◯}(\frac{1}{\hat{I}}\mu \log \frac{1}{\hat{I}}\mu )$ queries.