Efficiently Testing Digital Convexity and Recognizing Digital Convex Polygons

摘要

A set S subset of Z(2) of integer points is digital convex if conv(S) boolean AND Z(2) = S, where conv(S) denotes the convex hull of S. In this paper, we consider the following two problems. The first one is to test whether a given set S of n lattice points is digital convex. If the answer to the first problem is positive, then the second problem is to find a polygon P subset of Z(2) with minimum number of edges and whose intersection with the lattice P boolean AND Z(2) is exactly S. We provide linear-time algorithms for these two problems. The algorithm is based on the well-known quickhull algorithm. The time to solve both problems is O(n + h log r) = O(n + n(1/3) log r), where h = min(vertical bar conv(S)vertical bar, n(1/3)) and r is the diameter of S.