An Output Sensitive Algorithm for Discrete Convex Hulls
Home Bookmarks Papers Blog

An Output Sensitive Algorithm for Discrete Convex Hulls

Sariel Har-Peled


Given a convex body C in the plane, its discrete hull is C0 = ConvexHull( C \cap L), where L = Z*Z is the integer lattice. We present an O( |C0| log D(C))-time algorithm for calculating the discrete hull of C, where |C0| denotes the number of vertices of C0, 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.


PS : PDF
@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
}

Last modified: Fri Nov 14 11:12:47 CST 2014