
arXiv: 2312.03681
We investigate algorithms for testing whether an image is connected. Given a proximity parameter $ε\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 $ε$-far from connected. We show that connectedness can be tested nonadaptively with $O(\frac 1{ε^2})$ queries and adaptively with $O(\frac{1}{ε^{3/2}} \sqrt{\log\frac{1}ε})$ queries. The best connectedness tester to date, by Berman, Raskhodnikova, and Yaroslavtsev (STOC 2014) had query complexity $O(\frac 1{ε^2}\log \frac 1ε)$ and was adaptive. We also prove that every nonadaptive, 1-sided error tester for connectedness must make $Ω(\frac 1ε\log \frac 1ε)$ queries.
graphs, FOS: Computer and information sciences, sublinear algorithms, Property testing, property testing, 004, Graph theory, lower bounds, sublinear-algorithms, connectivity, Computer Science - Data Structures and Algorithms, computational geometry, Data Structures and Algorithms (cs.DS), Algorithms in computer science, ddc: ddc:004
graphs, FOS: Computer and information sciences, sublinear algorithms, Property testing, property testing, 004, Graph theory, lower bounds, sublinear-algorithms, connectivity, Computer Science - Data Structures and Algorithms, computational geometry, Data Structures and Algorithms (cs.DS), Algorithms in computer science, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
