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 language | English (US) |
---|---|
Pages (from-to) | 125-138 |
Number of pages | 14 |
Journal | Computational Geometry: Theory and Applications |
Volume | 10 |
Issue number | 2 |
DOIs | |
State | Published - May 1998 |
Externally published | Yes |
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