Testing Connectedness of Images

We investigate algorithms for testing whether an image is connected. Given a proximity parameter ε∈(0,1) and query access to a black-and-white image represented by an n× 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 ε-far from connected. We show that connectedness can be tested nonadaptively with O(frac 1ε2) queries and adaptively with O(frac1ε3/2 √logfrac1ε) queries. The best connectedness tester to date, by Berman, Raskhodnikova, and Yaroslavtsev (STOC 2014) had query complexity O(frac 1ε2log frac 1ε) and was adaptive. We also prove that every nonadaptive, 1-sided error tester for connectedness must make Omega(frac 1εlog frac 1ε) queries.