TY - JOUR
ID - 71276
TI - Sweep Line Algorithm for Convex Hull Revisited
JO - Journal of Algorithms and Computation
JA - JAC
LA - en
SN - 2476-2776
AU - Borna, Keivan
AD - Faculty of
Mathematics and Computer Science, Kharazmi University, Tehran,
Iran
Y1 - 2019
PY - 2019
VL - 51
IS - 1
SP - 1
EP - 14
KW - convex hull
KW - sweep-line method
KW - computational geometry
KW - graham scan
KW - time complexity
KW - Performance
DO - 10.22059/jac.2019.71276
N2 - Convex hull of some given points is the intersection of all convex sets containing them. It is used as primary structure in many other problems in computational geometry and other areas like image processing, model identification, geographical data systems, and triangular computation of a set of points and so on. Computing the convex hull of a set of point is one of the most fundamental and important problems of computational geometry. In this paper a new algorithm is presented for computing the convex hull of a set of random points in the plane by using a sweep-line strategy. The sweep-line is a horizontal line that is moved from top to bottom on a map of points. Our algorithm is optimal and has time complexity $O(nlogn)$ where $n$ is the size of input.
UR - https://jac.ut.ac.ir/article_71276.html
L1 - https://jac.ut.ac.ir/article_71276_3582cee25a2b43cca2ab21531a548870.pdf
ER -