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

Abstract

Consider a finite non-vertical, and non-degenerate straight-line segment s = [s ₀; s ₁] in the Euclidian plane $\mathbb{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(s ₀); x(s ₁)]. 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 ²) time, compared with O(k) for the first.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.