An Output Sensitive Algorithm for Discrete Convex Hulls

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