TY - JOUR
T1 - Testing Connectedness of Images
AU - Berman, Piotr
AU - Murzabulatov, Meiram
AU - Raskhodnikova, Sofya
AU - Ristache, Dragos Florian
N1 - Publisher Copyright:
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2024.
PY - 2024
Y1 - 2024
N2 - 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.
AB - 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.
KW - Computational geometry
KW - Property testing
KW - Sublinear algorithms
UR - http://www.scopus.com/inward/record.url?scp=85203701197&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85203701197&partnerID=8YFLogxK
U2 - 10.1007/s00453-024-01248-x
DO - 10.1007/s00453-024-01248-x
M3 - Article
AN - SCOPUS:85203701197
SN - 0178-4617
JO - Algorithmica
JF - Algorithmica
ER -