An Output Sensitive Algorithm for Discrete Convex Hulls

Sariel Har-Peled

Given a convex body C in the plane, its discrete hull is C⁰ = ConvexHull( C \cap L), where L = Z*Z is the integer lattice. We present an O( |C⁰| log D(C))-time algorithm for calculating the discrete hull of C, where |C⁰| denotes the number of vertices of C⁰, and D(C) is the diameter of C. Actually, using known combinatorial bounds, the running time of the algorithm is O(D(C)^2/3 log D(C)). In particular, this bound applies when C is a disk.

In Computational Geometry: Theory and Applications, 10 (1998) 125-138.
A preliminary version appeared in the 14th ACM Symp. of Comput. Geom., 1998.

Postscript file

@Article{hp-osafd-98a,
  author =       {S.~Har-Peled}
, title =        {An Output Sensitive Algorithm for Discrete Convex Hulls}
, volume =      10
, pages = {125--138}
, journal =      CGTA
, year =         1998
}