An output sensitive algorithm for discrete convex hulls
Sariel Har-Peled · 1998
Given a convex body C in the plane, its discrete hull is Co s ConvexHull(C I-I C), where C = Z x Z is the integer lattice.We present an O(lC"l logC(C))-time algorithm for calculating the discrete hull of C, where IC"l denote5 the number of vertices of Co, and a(C) is the diameter of C. Actually, using known combinatorial bounds, the running time of the algorithm is 0(6(C)als log J(C)).In particular, this bound applies when C is a disk.