Full Text:   <1814>

CLC number: TP391

On-line Access: 

Received: 2006-11-07

Revision Accepted: 2007-05-14

Crosschecked: 0000-00-00

Cited: 4

Clicked: 2941

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2007 Vol.8 No.8 P.1210~1217

http://doi.org/10.1631/jzus.2007.A1210


A new algorithm for computing the convex hull of a planar point set


Author(s):  LIU Guang-hui, CHEN Chuan-bo

Affiliation(s):  College of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China

Corresponding email(s):   aaalgh@263.net

Key Words:  Computational geometry, Convex hull, Extreme points, Ordered convex hull point sequence


LIU Guang-hui, CHEN Chuan-bo. A new algorithm for computing the convex hull of a planar point set[J]. Journal of Zhejiang University Science A, 2007, 8(8): 1210~1217.

@article{title="A new algorithm for computing the convex hull of a planar point set",
author="LIU Guang-hui, CHEN Chuan-bo",
journal="Journal of Zhejiang University Science A",
volume="8",
number="8",
pages="1210~1217",
year="2007",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2007.A1210"
}

%0 Journal Article
%T A new algorithm for computing the convex hull of a planar point set
%A LIU Guang-hui
%A CHEN Chuan-bo
%J Journal of Zhejiang University SCIENCE A
%V 8
%N 8
%P 1210~1217
%@ 1673-565X
%D 2007
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2007.A1210

TY - JOUR
T1 - A new algorithm for computing the convex hull of a planar point set
A1 - LIU Guang-hui
A1 - CHEN Chuan-bo
J0 - Journal of Zhejiang University Science A
VL - 8
IS - 8
SP - 1210
EP - 1217
%@ 1673-565X
Y1 - 2007
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2007.A1210


Abstract: 
When the edges of a convex polygon are traversed along one direction, the interior of the convex polygon is always on the same side of the edges. Based on this characteristic of convex polygons, a new algorithm for computing the convex hull of a simple polygon is proposed in this paper, which is then extended to a new algorithm for computing the convex hull of a planar point set. First, the extreme points of the planar point set are found, and the subsets of point candidate for vertex of the convex hull between extreme points are obtained. Then, the ordered convex hull point sequences between extreme points are constructed separately and concatenated by removing redundant extreme points to get the convex hull. The time complexity of the new planar convex hull algorithm is O(nlogh), which is equal to the time complexity of the best output-sensitive planar convex hull algorithms. Compared with the algorithm having the same complexity, the new algorithm is much faster.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1] Bhattacharya, B.K., Sen, S., 1997. On a simple, practical, optimal, output-sensitive randomized planar convex hull algorithm. Journal of Algorithms, 25(1):177-193.

[2] Brönnimann, H., Iacono, J., Katajainen, J., Morin, P., Morrison, J., Toussaint, G., 2004. Space-efficient planar convex hull algorithms. Theor. Computer Sci., 321(1):25-40.

[3] Brönnimann, H., Chan, T.M., 2006. Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time. Comput. Geom., 34(2):75-82.

[4] Cui, G.H., Hong, F., Yu, X.X., 1997. A class of optimal algorithms for determine the convex hull of a set of nodes in a plane. Chin. J. Computers, 20(4):330-334 (in Chinese).

[5] Jin, W.H., He, T., Liu, X.P., Tang, W.Q., Tang, R.X., 1998. A fast convex hull algorithm of planar point set based on sorted simple polygon. Chin. J. Computers, 21(6):533-539 (in Chinese).

[6] Joswig, M., Ziegler, G.M., 2004. Convex hulls, oracles, and homology. J. Symb. Comput., 38:1247-1259.

[7] Kirkpatrick, D.G., Seidel, R., 1986. The ultimate planar convex hull algorithm? SIAM J. Computers, 15(1):287-299.

[8] Kong, X.S., Cai, H.X., 1994. An algorithm for finding the convex hull of a simple polygon using active double line testing. Chin. J. Computers, 17(8):596-600 (in Chinese).

[9] Lee, T.D., 1983. On finding the convex hull of a simple polygon. Int. J. Comp. & Inf., 12(2):87-98.

[10] Levcopoulos, C., Lingas, A., Mitchell, J.S.B., 2002. Adaptive Algorithms for Constructing Convex Hulls and Triangulations of Polygonal Chains. 8th Scandinavian Workshop on Algorithm Theory. Turku, FL, p.80-89.

[11] Liu, J.Y., 2002. Discussion on an O(n) time algorithm for the convex hull of a planar point set. Chin. J. Computers, 25(6):670-672 (in Chinese).

[12] McCallum, D., Avis, D., 1979. A linear algorithm for finding the convex hull of a simple polygon. Inf. Processing Lett., 9:201-206.

[13] Melkman, A.A., 1987. On-line construction of the convex hull of a simple polygon. Inf. Processing Lett., 25(1):11-12.

[14] O′Rourke, J., 1998. Computational Geometry in C (2nd Ed.). Cambridge University Press, Cambridge.

[15] Preparata, F.P., Shamos, M.I., 1985. Computational Geometry: An Introduction. Springer-Verlag, New York, p.45-46.

[16] Sklansky, J., 1972. Measuring concavity on a rectangular mosaic. IEEE Trans. on Comput., C-21(12):1355-1364.

[17] Wang, Z.Q., Hong, J.Z., Xiao, L.J., 1998. An optimal real time algorithm for determine the convex hull of a set of points in a plane. Chin. J. Computers, 21(Suppl.):351-356 (in Chinese).

[18] Wu, Z.H., Ye, C.Q., Pan, Y.H., 1997. An improved algorithm of convex hull computing. J. Computer-Aided Design & Computer Graphics, 9(1):9-13 (in Chinese).

[19] Yao, C.A., 1981. A lower bound to finding convex hulls. J. ACM, 28(4):780-787.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE