An output sensitive algorithm for discrete convex hulls

Research output: Contribution to journalArticlepeer-review

Abstract

Given a convex body C in the plane, its discrete hull is C0 = ConvexHull(C ∩ ℒ), where ℒ = ℤ × ℤ is the integer lattice. We present an O(|C0| log δ(C))-time algorithm for calculating the discrete hull of C, where |C0| denotes the number of vertices of C0, and δ(C) is the diameter of C. Actually, using known combinatorial bounds, the running time of the algorithm is O(δ(C)2/3 log δ(C)). In particular, this bound applies when C is a disk.

Original languageEnglish (US)
Pages (from-to)125-138
Number of pages14
JournalComputational Geometry: Theory and Applications
Volume10
Issue number2
DOIs
StatePublished - May 1998
Externally publishedYes

Keywords

  • Continued fractions
  • Convex hull
  • Discrete hull

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'An output sensitive algorithm for discrete convex hulls'. Together they form a unique fingerprint.

Cite this