A Quick Convex Hull Building Algorithm Based on Grid and Binary Tree

GAO Yang; CHENG Yuhu; WANG Xuesong

doi:10.1049/cje.2015.04.015

Volume 24 Issue 2

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2015 > 24(2): 317-320

GAO Yang, CHENG Yuhu, WANG Xuesong, “A Quick Convex Hull Building Algorithm Based on Grid and Binary Tree,” Chinese Journal of Electronics, vol. 24, no. 2, pp. 317-320, 2015, doi: 10.1049/cje.2015.04.015

Citation:

GAO Yang, CHENG Yuhu, WANG Xuesong, “A Quick Convex Hull Building Algorithm Based on Grid and Binary Tree,” Chinese Journal of Electronics, vol. 24, no. 2, pp. 317-320, 2015, doi: 10.1049/cje.2015.04.015

Citation:

PDF( 324 KB)

A Quick Convex Hull Building Algorithm Based on Grid and Binary Tree

doi: 10.1049/cje.2015.04.015

School of Information and Electrical Engineering, China University of Mining and Technology, Xuzhou 221116, China

Funds: This work is supported by National Natural Science Foundation of China (No.61273143, No.61472424), Specialized Research Fund for the Doctoral Program of Higher Education of China (No.20120095110025) and Fundamental Research Funds for the Central Universities (No.2013RC10, No.2013RC12, No.2014YC07).

More Information

Corresponding author: WANG Xuesong received the Ph.D. degree from China University of Mining and Technology in 2002. She is currently a professor in the School of Information and Electrical Engineering, China University of Mining and Technology. Her main research interests include machine learning and artificial intelligence. (Email:wangxuesongcumt@163.com)
Publish Date: 2015-04-10

Abstract

Abstract

A quick convex hull building algorithm using grid and binary tree is proposed for the minimum convex buidling of planar point set. Grids are used to assess and eliminate those interior points wihtout any contribution to convex hull building and points are sought in the boundary grid only so as to enhance the efficiency of algorithm. The minimum convex bull is built by taking such advantages of binary tree as quick, convenient and applicable for various point sets with different distributions, so as to resolve the description problem of concave point. The time complexity of the algorithm is low because of grid pretreatment. As the results of comparative expriment of random point and actual picture show, the proposed algorithm can obtain the best profile of 2D planar picture with minimum time, which is applicable for describing the shape of irregular convex-concave objects.
- Convex hull,
- Gird,
- Binary tree,
- Concave point,
- Time complexity

FullText(HTML)

References(14)

References

H.C. Thomas, E.L. Charles, L. Ronald and S. Clifford, Introduction to Algorithms, Second Edition, MIT Press and McGraw- Hill, pp.955-956, 2001.

V.D. Obade and R. Lal, “Assessing land cover and soil quality by remote sensing and geographical information systems (GIS)”, Catena, Vol.104, No.1, pp.77-92, 2013.

J. Bai and X.C. Feng, “Image denoising and decomposition using non-convex functional”, Chinese Journal of Electronics, Vol.21, No.1, pp.102-106, 2012.

M.I. Karavelas, R. Seidel and E. Tzanaki, “Convex hulls of spheres and convex hulls of disjoint convex polytopes”, Computational Geometry-theory and Applications, Vol.46, No.6, pp.615-630, 2013.

L.Y. Ma and J. Yu, “A convex approach for local statistics based region segmentation”, Chinese Journal of Electronics, Vol.21, No.4, pp.623-626, 2012.

W.M. Cao and L.J. Ding, “Cancer subtypes recognition and its gene expression profiles analysis based on geometrical learning”, Chinese Journal of Electronics, Vol.15, No.4, pp.891-894, 2006.

Y. Davydov and C. Dombry, “Asymptotic behavior of the convex hull of a stationary Gaussian process”, Lithuanian Mathematical Journal, Vol.52, No.4, pp.363-368, 2012.

L. Cinque and M.C. Di, “A BSP realization of Jarvis' algorithm”, Pattern Recognition Letters, Vol.22, No.2, pp.147-155, 2001.

H. Ratschek and J. Rokne, “Exact and optimal convex hulls in 2D”, International Journal of Computational Geometry & Applications, Vol.10, No.2, pp.109-129, 2000.

C.D. Castanho, W. Chen and K. Wada, “A parallel algorithm for constructing strongly convex superhulls of points”, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, Vol.E83A, No.4, pp.722-732, 2000.

J.S. Fan, S.W. Xiong and J.Z. Wang, “The multi-objective differential evolution algorithm based on quick convex hull algorithms”, Proc. of the 5th International Conference on Natural Computation, Tianjin, China, pp.469-473, 2009.

J.H. Wang and Y.M. Chen, “A gird-aided algorithm for determining the minimum convex hull of planar points set”, Geomatics and Information Science of Wuhan University, Vol.35, No.4, pp.403-406, 2010. (in Chinese)

S.D. Li, D.S. Wang and Y.Q. Dai, “Efficient secure multiparty computational geometry”, Chinese Journal of Electronics, Vol.19, No.2, pp.324-328, 2010.

M. Sharif, S. Khan, S.J. Khan and M. Raza, “An algorithm to find convex hull based on binary tree”, Proc. of the IEEE 13th International Multitopic Conference, Islamabad, Pakistan, pp.1-6, 2009.

Relative Articles

Supplements(0)

Cited By

Proportional views