An Output Sensitive Algorithm for Discrete Convex Hulls

Abstract

Given a convex body $C$ in the plane, its discrete hull is $C^0 = \CH( C \cap \LL )$, where $\LL = \ZZ \times \ZZ$ is the integer lattice. We present an $O( |C^0| \log \DD(C) )$-time algorithm for calculating the discrete hull of $C$, where $|C^0|$ denotes the number of vertices of $C^0$, and $\DD(C)$ is the diameter of $C$. Actually, using known combinatorial bounds, the running time of the algorithm is $O(\DD(C)^{2/3} \log{\DD(C)})$. In particular, this bound applies when $C$ is a disk.

Appeared in SoCG 98