An output sensitive algorithm for discrete convex hulls

Sariel Har-Peled

doi:10.1016/S0925-7721(97)00031-X

An output sensitive algorithm for discrete convex hulls

Research output: Contribution to journal › Article › peer-review

Abstract

Given a convex body C in the plane, its discrete hull is C⁰ = ConvexHull(C ∩ ℒ), where ℒ = ℤ × ℤ is the integer lattice. We present an O(|C⁰| log δ(C))-time algorithm for calculating the discrete hull of C, where |C⁰| denotes the number of vertices of C⁰, 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	https://doi.org/10.1016/S0925-7721(97)00031-X
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

Online availability

10.1016/S0925-7721(97)00031-X

Library availability

Discover UIUC Full Text

Cite this

@article{3c5e068e64ba45e485af8fc0521666e0,

title = "An output sensitive algorithm for discrete convex hulls",

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.",

keywords = "Continued fractions, Convex hull, Discrete hull",

author = "Sariel Har-Peled",

note = "Funding Information: ~ This work has been supported by a grant from the U.S.-Israeli Binational Science Foundation. This work is part of the author's Ph.D. Thesis, prepared at Tel Aviv University under the supervision of Prof. Micha Sharir. ~ E-mail: sariel @ math.tau.ac.il.",

year = "1998",

month = may,

doi = "10.1016/S0925-7721(97)00031-X",

language = "English (US)",

volume = "10",

pages = "125--138",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - An output sensitive algorithm for discrete convex hulls

AU - Har-Peled, Sariel

N1 - Funding Information: ~ This work has been supported by a grant from the U.S.-Israeli Binational Science Foundation. This work is part of the author's Ph.D. Thesis, prepared at Tel Aviv University under the supervision of Prof. Micha Sharir. ~ E-mail: sariel @ math.tau.ac.il.

PY - 1998/5

Y1 - 1998/5

N2 - 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.

AB - 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.

KW - Continued fractions

KW - Convex hull

KW - Discrete hull

UR - http://www.scopus.com/inward/record.url?scp=0040757539&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0040757539&partnerID=8YFLogxK

U2 - 10.1016/S0925-7721(97)00031-X

DO - 10.1016/S0925-7721(97)00031-X

M3 - Article

AN - SCOPUS:0040757539

SN - 0925-7721

VL - 10

SP - 125

EP - 138

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 2

ER -

An output sensitive algorithm for discrete convex hulls

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this