APPROXIMATING VERTICES OF A CONVEX POLYGON WITH GRID POINTS IN THE POLYGON

Abstract

In this paper, we consider the problem of approximating a vertex of a convex polygon by an integer point in the polygon. We show that the nearest grid point in a convex polygon to a vertex can be found if it exists, or decided to be nonexistent, in time O(n + logl), where l is the diameter of the polygon and a is the number of the polygon's vertices. The underlying technique used in the continued fraction expansion.