REGULAR ENUMERATION OF GRID POINTS IN A CONVEX POLYGON

Abstract

In this paper we present an efficient algorithm for enumerating all the grid points in a convex polygon, where the enumeration is done by scanning the grid points with a set of parallel grid lines. Given a convex n-gon, enumeration can be done in O(K + + log min{root l/omega, l}) time, where K is the number of the grid points reported, l is the diameter of the polygon and omega is the length of the shorter sides of the rectangle enclosing the polygon with longer sides parallel to the line segment connecting the diametral pair of the polygon. We also show that the ratio of the number of the scanned grid lines to the minimal is less than some constant.