The power and limitations of uniform samples in testing properties of figures

DOI10.1007/S00453-018-0467-9zbMath1417.68225OpenAlexW2887874679WikidataQ129441456 ScholiaQ129441456MaRDI QIDQ666678

Meiram Murzabulatov, Sofya Raskhodnikova, Piotr Berman

Publication date: 11 March 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6880/

zbMATH Keywords

convexityrandomized algorithmsproperty testing2-dimensional geometrybeing a half-plane

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Convex sets in (2) dimensions (including convex curves) (52A10) Randomized algorithms (68W20)

Related Items (2)

A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification ⋮ Testing connectedness of images

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing periodicity
• Property testing. Current research and surveys
• Another efficient algorithm for convex hulls in two dimensions
• Self-testing/correcting with applications to numerical problems
• Spot-checkers
• Fast-Match: fast affine template matching
• Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy
• On Sample-Based Testers
• Testing Convexity of Figures Under the Uniform Distribution
• Property testing and its connection to learning and approximation
• Testing Symmetric Properties of Distributions
• Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
• The complexity of approximating entropy
• Monotonicity testing over general poset domains
• A sublinear algorithm for weakly approximating edit distance
• Partitioning with two lines in the plane
• Testing for Forbidden Order Patterns in an Array
• Tolerant testers of image properties
• The Power and Limitations of Uniform Samples in Testing Properties of Figures
• Parameterized property testing of functions
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing Properties of Sparse Images
• Optimal unateness testers for real-valued functions: Adaptivity helps
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• lgorithmic and Analysis Techniques in Property Testing
• L _p -testing
• Introduction to Property Testing
• Testing Closeness of Discrete Distributions
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Some 3CNF Properties Are Hard to Test
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Testing monotonicity
• Property testing in bounded degree graphs

This page was built for publication: The power and limitations of uniform samples in testing properties of figures