×

A modification of Graham’s algorithm for determining the convex hull of a finite planar set. (English) Zbl 1135.52303

Summary: In this paper, in our modification of Graham scan for determining the convex hull of a finite planar set, we show a restricted area of the examination of points and its advantage. The actual run times of our scan and Graham scan on the set of random points shows that our modified algorithm runs significantly faster than Graham’s one.

MSC:

52B55 Computational aspects related to convexity
52C45 Combinatorial complexity of geometric structures
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDFBibTeX XMLCite
Full Text: EuDML