2023/02/15 by Adrian Dumitrescu, Dumitrescu, Adrian
Computer Science · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2302.07423
openalex publication_date 2023/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We revisit the problem of property testing for convex position for point sets in ℝd. Our results draw from previous ideas of Czumaj, Sohler, and Ziegler (ESA 2000). First, the algorithm is redesigned and its analysis is revised for correctness. Second, its functionality is expanded by (i)~exhibiting both negative and positive certificates along with the convexity determination, and (ii)~significantly extending the input range for moderate and higher dimensions. The behavior of the randomized tester is as follows: (i)~if P is in convex position, it accepts; (ii)~if P is far from convex position, with probability at least 2/3, it rejects and outputs a (d+2)-point witness of non-convexity as a negative certificate; (iiii)~if P is close to convex position, with probability at least 2/3, it accepts and outputs an approximation of the largest subset in convex position. The algorithm examines a sublinear number of points and runs in subquadratic time for every dimension d.