Testing Connectedness of Images
Berman P. Murzabulatov M. Raskhodnikova S. Ristache D.-F.
November 2024Springer
Algorithmica
2024#86Issue 113496 - 3517 pp.
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(1ϵ2) queries and adaptively with O(1ϵ3/2log1ϵ) queries. The best connectedness tester to date, by Berman, Raskhodnikova, and Yaroslavtsev (STOC 2014) had query complexity O(1ϵ2log1ϵ) and was adaptive. We also prove that every nonadaptive, 1-sided error tester for connectedness must make Ω(1ϵlog1ϵ) queries.
Computational geometry , Property testing , Sublinear algorithms
Text of the article Перейти на текст статьи
Nazarbayev University, Astana, Kazakhstan
Boston University, Boston, United States
Nazarbayev University
Boston University
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026