article · ArXiv.org · 2026

An Output Sensitive Algorithm for Discrete Convex Hulls

Har-Peled, Sariel

Cited by 0Open access

Abstract

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

Cite this paper

APA 7

Har-Peled, S. (2026). An Output Sensitive Algorithm for Discrete Convex Hulls. ArXiv.org.

MLA 9

Har-Peled, Sariel. “An Output Sensitive Algorithm for Discrete Convex Hulls.” ArXiv.org, 2026.

Chicago

Har-Peled, Sariel. 2026. “An Output Sensitive Algorithm for Discrete Convex Hulls.” ArXiv.org.

Harvard

Har-Peled, S. (2026) ‘An Output Sensitive Algorithm for Discrete Convex Hulls’, ArXiv.org.

BibTeX

@article{harpeled2026output,
  title = {{An Output Sensitive Algorithm for Discrete Convex Hulls}},
  author = {Har-Peled, Sariel},
  journal = {ArXiv.org},
  year = {2026}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.