Testing Connectedness of Images

Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova, Dragos Florian Ristache

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
JournalAlgorithmica
DOIs
Publication statusAccepted/In press - 2024

Keywords

  • Computational geometry
  • Property testing
  • Sublinear algorithms

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Testing Connectedness of Images'. Together they form a unique fingerprint.

Cite this