Constructing the convex hull of a planar density-bounded integral-points set in linear time
Junhui Deng, Zesheng Tang, Meihe Xu · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1996
A special kind of points sets named DPDIS is defined in this paper, followed by an elegant algorithm for constructing the convex hull of this class of points sets. Taking advantages of the characteristics of this sets category, this algorithm finishes its work within an O(N) complexity. The crux of this algorithm is a new sorting method by which all points can be sorted along x direction in linear time.