| We conduct a systematic study of sublinear-time algorithms for geometric properties of images. We investigate three fundamental properties: being a half-plane, convexity, and connectedness. For all three properties, we study the query and time complexity of property testing and tolerant property testing in different variants of the models: with different types of access to the input and restrictions on the algorithms.;A property tester is adaptive if its queries depend on the answers to its previous queries. Otherwise, the tester is nonadaptive. For the half-plane property, we give the first nonadaptive property tester whose running time and query complexity is optimal. For convexity, we design the first adaptive tester with optimal query and time complexity. We also improve the previously known nonadaptive tester for this property. For connectedness, we design the first nonadaptive tester and improve the previously known adaptive tester.;We design algorithms that approximate the distance to the three properties within a small additive error or, equivalently, tolerant testers for being a half-plane, convexity, and connectedness. Previously, no tolerant testing algorithms were known for these properties. Designing tolerant testers for image properties is important, since images are often noisy and tolerant testers are robust to noise. |
