Convex Hull of Grid Points below a Line or a Convex Curve

Consider a finite non-vertical, and non-degenerate straight-line segment s = [s0 ; s1 ] in the Euclidian plane E 2 . We give a method for constructing the boundary of the upper convex hull of all the points with integral coordinates below (or on) s, with abscissa in [x(s0); x(s1 )]. The algorithm takes O(log n) time, if n is the length of the segment. We next show how to perform a similar construction in the case where s is a finite, non-degenerate, convex arc on a quadric curve. The associated method runs in O(k log n), where n is the arc's length and k the number of vertices on the boundary of the resulting hull. This method may also be used for a line segment; in this case, k = O(log n), and the second method takes O(k 2 ) time, compared with O(k) for the first. 1 Upper Hull of Grid Points below a Line Segment This paper will consider integral hulls, i.e. convex hulls of set of points with integral coordinates in the Euclidean plane (grid points). A paper on 3D lattice convex ..