# Testing Connectedness of Images

arXiv: https://arxiv.org/abs/2312.03681 · HTML: https://mlsanity.com/paper/2312.03681/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Dec 2023.

## Built on by (most cited first, 1 of 1)

- [Fast Agnostic Learners in the Plane](https://mlsanity.com/paper/2510.18057/) (2025)

## Abstract (arXiv)

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.