Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2312.03681 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910507130159104 |
|---|---|
| author | Berman, Piotr Murzabulatov, Meiram Raskhodnikova, Sofya Ristache, Dragos-Florian |
| author_facet | Berman, Piotr Murzabulatov, Meiram Raskhodnikova, Sofya Ristache, Dragos-Florian |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_03681 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Testing Connectedness of Images Berman, Piotr Murzabulatov, Meiram Raskhodnikova, Sofya Ristache, Dragos-Florian Data Structures and Algorithms 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. |
| title | Testing Connectedness of Images |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2312.03681 |