×

\(\alpha\)-concave hull, a generalization of convex hull. (English) Zbl 1380.68376

Summary: Bounding hulls such as convex hull, \(\alpha\)-shape, \(\chi\)-hull, concave hull, crust, etc. offer a wide variety of useful applications. In this paper, we explore another bounding hull, namely \(\alpha\)-concave hull, as a generalization of convex hull. The parameter \(\alpha\) determines the smoothness level of the constructed hull on a set of points. We show that it is NP-hard to compute \(\alpha\)-concave hull on a set of points for any \(0<\alpha<\pi\). This leads us to a generalization of Fekete work (when \(\alpha=\pi\)). We also introduce \(\alpha\)-MACP as an NP-hard problem similar to the problem of computing \(\alpha\)-concave hull and present an approximation algorithm for \(\alpha\)-MACP. The paper ends by implementing the proposed algorithm and comparing the experimental results against those of convex hull and \(\alpha\)-shape models.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25 Approximation algorithms

Software:

BetaSCP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Toussaint, G. T., A historical note on convex hull finding algorithms, Pattern Recognit. Lett., 3, 1, 21-28 (1985)
[2] o’Rourke, J., Computational Geometry in C (1998), Cambridge University Press · Zbl 0912.68201
[3] Graham, R. L., An efficient algorithm for determining the convex hull of a finite planar set, Inform. Process. Lett., 1, 4, 132-133 (1972) · Zbl 0236.68013
[4] Chand, D. R.; Kapur, S. S., An algorithm for convex polytopes, J. ACM, 17, 1, 78-86 (1970) · Zbl 0199.50902
[5] Jarvis, R. A., On the identification of the convex hull of a finite set of points in the plane, Inform. Process. Lett., 2, 1, 18-21 (1973) · Zbl 0256.68041
[6] Eddy, W. F., A new convex hull algorithm for planar sets, ACM Trans. Math. Software, 3, 4, 398-403 (1977) · Zbl 0374.68036
[7] Preparata, F. P.; Hong, S. J., Convex hulls of finite sets of points in two and three dimensions, Commun. ACM, 20, 2, 87-93 (1977) · Zbl 0342.68030
[8] Kallay, M., The complexity of incremental convex hull algorithms in \(R^d\), Inform. Process. Lett., 19, 4, 197 (1984) · Zbl 0549.68036
[9] Corney, J.; Rea, H.; Clark, D.; Pritchard, J.; Breaks, M.; MacLeod, R., Coarse filters for shape matching, IEEE Comput. Graph. Appl., 22, 3, 65-74 (2002)
[10] Zhang, L.-H.; Xu, W.-L., Convex hull based point pattern matching under perspective transformation, Acta Automat. Sinica, 28, 2, 306-309 (2002) · Zbl 1498.68289
[11] Yang, Z.; Cohen, F. S., Image registration and object recognition using affine invariants and convex hulls, IEEE Trans. Image Process., 8, 7, 934-946 (1999) · Zbl 0948.68204
[12] Wen, C.; Guo, T., An efficient algorithm for fingerprint matching based on convex hulls, (International Conference on Computational Intelligence and Natural Computing, vol. 1, 2009. International Conference on Computational Intelligence and Natural Computing, vol. 1, 2009, CINC’09 (2009), IEEE), 66-69
[13] Liu, J.; Wang, X.; Zhuang, D., Application of convex hull in identifying the types of urban land expansion, Acta Geogr. Sin., 58, 6, 885-892 (2003)
[14] Peng, R.-C.; Wang, J.-Y.; Tian, Z.; Guo, L.-X.; Chen, Z.-P., A research for selecting baseline point of the territorial sea based on technique of the convex hull construction, Cehui Xuebao/Acta Geodaet. Cartograph. Sin., 34, 1, 53-57 (2005)
[15] Meeran, S.; Share, A., Optimum path planning using convex hull and local search heuristic algorithms, Mechatronics, 7, 8, 737-756 (1997)
[16] Fekete, S. P.; Pulleyblank, W. R., Area optimization of simple polygons, (Proceedings of the Ninth Annual Symposium on Computational Geometry (1993), ACM), 173-182
[17] Fekete, S. P., On simple polygonalizations with optimal area, Discrete Comput. Geom., 23, 1, 73-110 (2000) · Zbl 0948.68128
[18] Fekete, S. P., Geometry and the Travelling Salesman Problem (1992), University of Waterloo
[19] Bae, S. W.; Cho, H.-G.; Evans, W.; Saeedi, N.; Shin, C.-S., Covering points with convex sets of minimum size, Theor. Comput. Sci. (2016), in press
[20] Park, J.-S.; Oh, S.-J., A new concave hull algorithm and concaveness measure for \(n\)-dimensional datasets, JISE J. Inf. Sci. Eng., 29, 2, 379-392 (2013)
[21] Galton, A.; Duckham, M., What is the region occupied by a set of points?, (Geographic Information Science (2006), Springer), 81-98
[22] Moreira, A.; Santos, M. Y., Concave hull: A k-nearest neighbours approach for the computation of the region occupied by a set of points (2007), INSTICC Press (Institute for Systems and Technologies of Information, Control and Communication)
[23] Vishwanath, A.; Ramanathan, M., Concave hull of a set of freeform closed surfaces in \(R^3\), Comput-Aided Des. Appl., 9, 6, 857-868 (2012)
[24] Jones, J., Multi-agent slime mould computing: mechanisms, applications and advances, (Advances in Physarum Machines (2016), Springer), 423-463
[25] Siriba, D. N.; Matara, S. M.; Musyoka, S. M., Improvement of volume estimation of stockpile of earthworks using a concave hull-footprint, International Sci. J. Micro Macro Mezzo Geoinf., 5, 11-25 (2015)
[26] Chau, A. L.; Li, X.; Yu, W., Large data sets classification using convex-concave hull and support vector machine, Soft Comput., 17, 5, 793-804 (2013)
[27] Edelsbrunner, H.; Kirkpatrick, D.; Seidel, R., On the shape of a set of points in the plane, IEEE Trans. Inform. Theory, 29, 4, 551-559 (1983) · Zbl 0512.52001
[28] Edelsbrunner, H., Shape reconstruction with Delaunay complex, (Latin American Symposium on Theoretical Informatics (1998), Springer), 119-132 · Zbl 0905.65014
[29] Ganapathy, H.; Ramu, P.; Muthuganapathy, R., Alpha shape based design space decomposition for island failure regions in reliability based design, Struct. Multidiscip. Optim., 52, 1, 121-136 (2015)
[30] Fayed, M.; Mouftah, H. T., Localised alpha-shape computations for boundary recognition in sensor networks, Ad Hoc Netw., 7, 6, 1259-1269 (2009)
[31] Ryu, J.; Kim, D.-S., Protein structure optimization by side-chain positioning via beta-complex, J. Global Optim., 57, 1, 217-250 (2013) · Zbl 1277.90166
[32] Varytimidis, C.; Rapantzikos, K.; Avrithis, Y.; Kollias, S., \(α\)-Shapes for local feature detection, Pattern Recognit., 50, 56-73 (2016)
[33] Al-Tamimi, M. S.H.; Sulong, G.; Shuaib, I. L., Alpha shape theory for 3d visualization and volumetric measurement of brain tumor progression using magnetic resonance images, Magn. Reson. Imaging, 33, 6, 787-803 (2015)
[34] Amenta, N.; Bern, M.; Eppstein, D., The crust and the \(β\)-skeleton: combinatorial curve reconstruction, Graph. Models Image Process., 60, 2, 125-135 (1998)
[35] Amenta, N.; Bern, M.; Kamvysselis, M., A new Voronoi-based surface reconstruction algorithm, (Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques (1998), ACM), 415-421
[36] Duckham, M.; Kulik, L.; Worboys, M.; Galton, A., Efficient generation of simple polygons for characterizing the shape of a set of points in the plane, Pattern Recognit., 41, 10, 3224-3236 (2008) · Zbl 1147.68780
[37] R.G. Michael, S.J. David, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman & Co., San Francisco.; R.G. Michael, S.J. David, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman & Co., San Francisco. · Zbl 0411.68039
[38] Sherali, H. D.; Desai, J., A global optimization rlt-based approach for solving the hard clustering problem, J. Global Optim., 32, 2, 281-306 (2005) · Zbl 1123.62045
[39] Brucker, P., On the complexity of clustering problems, (Optimization and Operations Research (1978), Springer), 45-54 · Zbl 0397.68044
[40] Pick, G., Geometrisches zur zahlenlehre, Sitzenber. Lotos (Prague), 19, 311-319 (1899) · JFM 33.0216.01
[41] Bárány, I., Applications of graph and hypergraph theory in geometry, Combin. Comput. Geom., 52, 31-50 (2005) · Zbl 1090.05066
[42] Komlós, J.; Pintz, J.; Szemerédi, E., A lower bound for Heilbronn’s problem, J. Lond. Math. Soc. (2), 25, 1, 13-24 (1982) · Zbl 0483.52008
[43] Roth, K., On a problem of Heilbronn, III, Proc. Lond. Math. Soc. (3), 3, 3, 543-549 (1972) · Zbl 0253.52001
[44] Komlós, J.; Pintz, J.; Szemerédi, E., On Heilbronn’s triangle problem, J. Lond. Math. Soc. (2), 24, 2, 385-396 (1981) · Zbl 0483.52007
[45] Roth, K. F., On a problem of Heilbronn, J. Lond. Math. Soc. (2), 1, 3, 198-204 (1951) · Zbl 0043.16303
[46] Schmidt, W. M., On a problem of Heilbronn, J. Lond. Math. Soc. (2), 2, 3, 545-550 (1972) · Zbl 0233.52005
[47] Roth, K., On a problem of Heilbronn, II, Proc. Lond. Math. Soc. (3), 3, 2, 193-212 (1972) · Zbl 0248.52013
[48] Jiang, T.; Li, M.; Vitányi, P., The expected size of Heilbronn’s triangles, (Proceedings of Fourteenth Annual IEEE Conference on Computational Complexity (1999), IEEE), 105-113
[49] Barequet, G., A lower bound for Heilbronn’s triangle problem in d dimensions, SIAM J. Discrete Math., 14, 2, 230-236 (2001) · Zbl 0980.51017
[50] Lefmann, H., On Heilbronn’s problem in higher dimension, Combinatorica, 23, 4, 669-680 (2003) · Zbl 1099.68124
[51] Brass, P., An upper bound for the d-dimensional analogue of Heilbronn’s triangle problem, SIAM J. Discrete Math., 19, 1, 192-195 (2005) · Zbl 1091.51003
[52] Lefmann, H., Large triangles in the d-dimensional unit cube, Theoret. Comput. Sci., 363, 1, 85-98 (2006) · Zbl 1110.68109
[53] Barequet, G.; Shaikhet, A., The on-line Heilbronn’s triangle problem in \(d\) dimensions, Discrete Comput. Geom., 38, 1, 51-60 (2007) · Zbl 1132.52003
[54] Shaikhet, A., The On-line Heilbronn’s Triangle Problem in \(d\) Dimensions (2007), Technion - Israel Institute of Technology, Faculty of Computer Science · Zbl 1132.52003
[55] Chen, L.; Xu, Y.; Zeng, Z., Searching approximate global optimal Heilbronn configurations of nine points in the unit square via GPGPU computing, J. Global Optim., 1-21 (2016)
[56] Lien, J.-M., Approximate Convex Decomposition and Its Applications (2006), Texas A&M University, Ph.D. thesis
[57] Liu, R.; Zhang, H.; Busby, J., Convex hull covering of polygonal scenes for accurate collision detection in games, (Proceedings of Graphics Interface 2008 (2008), Canadian Information Processing Society), 203-210
[58] Ghosh, M.; Amato, N. M., Hierarchical distance-based aggregation (2014), Texas A&M University, Tech. rep., Technical Report TR1 4-006
[59] Zhang, D.; Lu, G., Review of shape representation and description techniques, Pattern Recognit., 37, 1, 1-19 (2004)
[60] Wischerhoff, M.; Plonka, G., Reconstruction of polygonal shapes from sparse Fourier samples, J. Comput. Appl. Math., 297, 117-131 (2016) · Zbl 1362.94012
[61] Igarashi, Y.; Suzuki, H., Cover geometry design using multiple convex hulls, Comput.-Aided Des., 43, 9, 1154-1162 (2011)
[62] Lucieer, A.; Kraak, M.-J., Alpha-shapes for visualizing irregular-shaped class clusters in 3d feature space for classification of remotely sensed imagery, (Electronic Imaging 2004 (2004), International Society for Optics and Photonics), 201-211
[63] Gong, W.; Liu, Y.-J.; Tang, K.; Wu, T., Approximate Delaunay mesh reconstruction and quality estimation from point samples, J. Comput. Appl. Math., 274, 23-34 (2015) · Zbl 1296.65027
[64] Dey, T. K.; Mehlhorn, K.; Ramos, E. A., Curve reconstruction: connecting dots with good reason, (Proceedings of the Fifteenth Annual Symposium on Computational Geometry (1999), ACM), 197-206
[65] Althaus, E.; Mehlhorn, K., Tsp-based curve reconstruction in polynomial time, (Proc. ACM-SIAM Sympos. Discrete Algorithms (2000)), Citeseer · Zbl 0954.65011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.