Boundary estimation from point clouds: algorithms, guarantees and applications. (English) Zbl 1492.65347
Summary: We investigate identifying the boundary of a domain from sample points in the domain. We introduce new estimators for the normal vector to the boundary, distance of a point to the boundary, and a test for whether a point lies within a boundary strip. The estimators can be efficiently computed and are more accurate than the ones present in the literature. We provide rigorous error estimates for the estimators. Furthermore we use the detected boundary points to solve boundary-value problems for PDE on point clouds. We prove error estimates for the Laplace and eikonal equations on point clouds. Finally we provide a range of numerical experiments illustrating the performance of our boundary estimators, applications to PDE on point clouds, and tests on image data sets.
MSC:
| 65N75 | Probabilistic methods, particle methods, etc. for boundary value problems involving PDEs |
| 62G20 | Asymptotic properties of nonparametric inference |
| 65N12 | Stability and convergence of numerical methods for boundary value problems involving PDEs |
| 65N15 | Error bounds for boundary value problems involving PDEs |
| 65D99 | Numerical approximation and computational geometry (primarily algorithms) |
References:
| [1] | Aamari, E., Aaron, C., Levrard, C.: Minimax boundary estimation and estimation with boundary, arXiv preprint arXiv:2108.03135 (2021) |
| [2] | Aamari, E.; Levrard, C., Nonasymptotic rates for manifold, tangent space and curvature estimation, Ann. Stat., 47, 177-204 (2019) · Zbl 1419.62130 |
| [3] | Aaron, C.; Cholaquidis, A., On boundary detection, Ann. Inst. Henri Poincaré Probab. Stat., 56, 2028-2050 (2020) · Zbl 1460.62054 |
| [4] | Adela DePavia, SS, Spectral clustering revisited: Information hidden in the Fiedler vector, Found. Data Sci., 3, 225-249 (2021) · Zbl 1483.31038 |
| [5] | Bardi, M., Capuzzo-Dolcetta, I.: Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations, Springer Science & Business Media (2008) · Zbl 1134.49022 |
| [6] | Barnett, V., The ordering of multivariate data, J. Royal Stat. Soc.: Ser. (General), 139, 318-344 (1976) |
| [7] | Bellock, K.: Alpha shape toolbox https://github.com/bellockk/alphashape. (accessed 2021/10/22) (2021) |
| [8] | Bentley, JL, Multidimensional divide-and-conquer, Commun. ACM, 23, 214-229 (1980) · Zbl 0434.68049 |
| [9] | Bentley, JL, Multidimensional divide-and-conquer, Discrete and Comp. Geom., 4, 101-115 (1989) |
| [10] | Bernhardsson, E.: Annoy: Approximate nearest neighbors in c++/python https://pypi.org/project/annoy/ (accessed 2020/10/19) (2018) |
| [11] | Berry, T.; Sauer, T., Density estimation on manifolds with boundary, Comput. Stat. Data Anal., 107, 1-17 (2017) · Zbl 1466.62029 |
| [12] | Birbrair, L.; Denkowski, MP, Medial axis and singularities, J. Geom. Anal., 27, 2339-2380 (2017) · Zbl 1380.32009 |
| [13] | Bou-Rabee, A., Morfe, P. S.: Hamilton-Jacobi scaling limits of pareto peeling in 2d, arXiv preprint arXiv:2110.06016, (2021) |
| [14] | Boucheron, S., Lugosi, G., Massart, P.: Concentration inequalities: A nonasymptotic theory of independence, Oxford university press (2013) · Zbl 1279.60005 |
| [15] | Calder, J., The game theoretic p-Laplacian and semi-supervised learning with few labels, Nonlinearity, 32, 301-330 (2018) · Zbl 1408.35048 |
| [16] | Calder, J.: Lecture notes on viscosity solutions, Online Lecture Notes http://www-users.math.umn.edu/ jwcalder/viscosity_solutions.pdf (2018) |
| [17] | Calder, J., Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data, SIAM J. Math. Data Sci., 1, 780-812 (2019) · Zbl 1499.35598 |
| [18] | Calder, J.: The calculus of variations, Online Lecture Notes http://www-users.math.umn.edu/ jwcalder/CalculusOfVariations.pdf (2020) |
| [19] | Calder, J.: Graph-based clustering and semi-supervised learning, https://github.com/jwcalder/GraphLearning. (accessed 2020/10/19) (2020) · Zbl 1465.35152 |
| [20] | Calder, J.; Esedoḡlu, S.; Hero, AO, A Hamilton-Jacobi equation for the continuum limit of non-dominated sorting, SIAM J. Math. Anal., 46, 603-638 (2014) · Zbl 1288.35190 |
| [21] | Calder, J., Ettehad, M.: Hamilton-Jacobi equations on graphs with applications to semi-supervised learning and data depth, In preparation (2021) |
| [22] | Calder, J., Trillos, N García: Improved spectral convergence rates for graph Laplacians on \(\varepsilon \)-graphs and k-NN graphs, arXiv:1910.13476 (2019) |
| [23] | Calder, J., Trillos, N. García, Lewicka, M.: Lipschitz regularity of graph Laplacians on random data clouds, arXiv:2007.06679 (2020) · Zbl 1485.35153 |
| [24] | Calder, J., Slepčev, D., Thorpe, M.: Rates of convergence for Laplacian semi-supervised learning with low labeling rates, arXiv:2006.02765 (2020) |
| [25] | Calder, J.; Smart, CK, The limit shape of convex hull peeling, Duke Math. J., 169, 2079-2124 (2020) · Zbl 1455.35047 |
| [26] | Cannarsa, P., Sinestrari, C.: Semiconcave functions, Hamilton-Jacobi equations, and optimal control, vol. 58, Springer Science & Business Media (2004) · Zbl 1095.49003 |
| [27] | Carrizosa, E., A characterization of halfspace depth, J. Multivar. Anal., 58, 21-26 (1996) · Zbl 0865.62036 |
| [28] | Chen, J-S; Hillman, M.; Chi, S-W, Meshfree methods: progress made after 20 years, J. Eng. Mech., 143, 04017001 (2017) |
| [29] | Chen, Y-C; Genovese, CR; Wasserman, L., Density level sets: asymptotics, inference, and visualization, J. Amer. Statist. Assoc., 112, 1684-1696 (2017) |
| [30] | Xia, Chenyi; Hsu, W.; Lee, M. L.; Ooi, BC, Border: efficient computation of boundary points, IEEE Trans. Knowl. Data Eng., 18, 289-303 (2006) |
| [31] | Chernozhukov, V.; Galichon, A.; Hallin, M.; Henry, M., Monge-kantorovich depth, quantiles, ranks and signs, Ann. Stat., 45, 223-256 (2017) · Zbl 1426.62163 |
| [32] | Costa, J.A., Hero, A. O.: Determining intrinsic dimension and entropy of high-dimensional shape spaces. In: Statistics and Analysis of Shapes, Springer, pp. 231-252 (2006) · Zbl 1160.94303 |
| [33] | Cuevas, A.; Fraiman, R., A plug-in approach to support estimation, Ann. Stat., 25, 2300-2312 (1997) · Zbl 0897.62034 |
| [34] | Cuevas, A.; Fraiman, R.; Györfi, L., Towards a universally consistent estimator of the Minkowski content, ESAIM Probab. Stat., 17, 359-369 (2013) · Zbl 1395.62069 |
| [35] | Cuevas, A.; Fraiman, R.; Rodríguez-Casal, A., A nonparametric approach to the estimation of lengths and surface areas, Ann. Statist., 35, 1031-1051 (2007) · Zbl 1124.62017 |
| [36] | Cuevas, A.; Rodríguez-Casal, A., On boundary estimation, Adv. in Appl. Probab., 36, 340-354 (2004) · Zbl 1045.62019 |
| [37] | de Micheaux, P. L., Mozharovskyi, P., Vimond, M.: Depth for curve data and applications, Journal of the American Statistical Association, pp. 1-17 (2020) |
| [38] | Devroye, L.; Wise, GL, Detection of abnormal behavior via nonparametric estimation of the support, SIAM J. Appl. Math., 38, 480-488 (1980) · Zbl 0479.62028 |
| [39] | Dong, W., Moses, C., Li, K.: Efficient k-nearest neighbor graph construction for generic similarity measures. In: Proceedings of the 20th International Conference on World Wide Web, WWW ’11, New York, NY, USA, Association for Computing Machinery, p. 577-586 (2011) |
| [40] | Edelsbrunner, H.: Alpha shapes-a survey, Tessellations in the Sciences (2010) |
| [41] | Edelsbrunner, H.; Kirkpatrick, D.; Seidel, R., On the shape of a set of points in the plane, IEEE Trans. Inf. Theory, 29, 551-559 (1983) · Zbl 0512.52001 |
| [42] | Edelsbrunner, H.; Mücke, EP, Three-dimensional alpha shapes, ACM Trans. Graph., 13, 43-72 (1994) · Zbl 0806.68107 |
| [43] | Finlay, C.; Oberman, A., Improved accuracy of monotone finite difference schemes on point clouds and regular grids, SIAM J. Sci. Comput., 41, A3097-A3117 (2019) · Zbl 1481.65204 |
| [44] | Flores, M., Calder, J., Lerman, G.: Analysis and algorithms for Lp-based semi-supervised learning on graphs, arXiv:1901.05031 (2019) |
| [45] | Flyer, N.; Wright, GB, A radial basis function method for the shallow water equations on a sphere, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 465, 1949-1976 (2009) · Zbl 1186.76664 |
| [46] | Foote, RL, Regularity of the distance function, Proceedings American Math. Soc., 92, 153-155 (1984) · Zbl 0528.53005 |
| [47] | Froese, BD, Meshfree finite difference approximations for functions of the eigenvalues of the Hessian, Numer. Math., 138, 75-99 (2018) · Zbl 1410.35037 |
| [48] | Fuselier, E.; Wright, GB, Scattered data interpolation on embedded submanifolds with restricted positive definite kernels: Sobolev error estimates, SIAM J. Numer. Anal., 50, 1753-1776 (2012) · Zbl 1251.41004 |
| [49] | García Trillos, N.; Gerlach, M.; Hein, M.; Slepčev, D., Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator, Found. Comput. Math., 20, 827-887 (2020) · Zbl 1447.62141 |
| [50] | García Trillos, N.; Murray, RW, A maximum principle argument for the uniform convergence of graph Laplacian regressors, SIAM J. Math. Data Sci., 2, 705-739 (2020) · Zbl 1485.35137 |
| [51] | Hein, M., Audibert, J.-Y.: Intrinsic dimensionality estimation of submanifolds in rd. In: Proceedings of the 22nd international conference on Machine learning, pp. 289-296 (2005) |
| [52] | Lachièze-Rey, R.; Vega, S., Boundary density and Voronoi set estimation for irregular sets, Trans. Amer. Math. Soc., 369, 4953-4976 (2017) · Zbl 1388.60042 |
| [53] | Lai, R.; Liang, J.; Zhao, H-K, A local mesh method for solving pdes on point clouds, Inverse Probl. Imaging, 7, 737 (2013) · Zbl 1273.65034 |
| [54] | LeCun, Y.; Bottou, L.; Bengio, Y.; Haffner, P., Gradient-based learning applied to document recognition, Proc. IEEE, 86, 2278-2324 (1998) |
| [55] | Li, Z.; Shi, Z.; Sun, J., Point integral method for solving poisson-type equations on manifolds from point clouds with convergence guarantees, Commun. Comput. Phys., 22, 228-258 (2017) · Zbl 1488.65714 |
| [56] | Liang, J.; Zhao, H., Solving partial differential equations on point clouds, SIAM J. Sci. Comput., 35, A1461-A1486 (2013) · Zbl 1275.65080 |
| [57] | Liang, S., Jiang, S. W. , Harlim, J., Yang, H.: Solving pdes on unknown manifolds with machine learning, arXiv:2106.06682 (2021) |
| [58] | Liu, RY; Parelius, JM; Singh, K., Multivariate analysis by data depth: descriptive statistics, graphics and inference,(with discussion and a rejoinder by liu and singh), Ann. Stat., 27, 783-858 (1999) · Zbl 0984.62037 |
| [59] | McMullen, P., The maximum numbers of faces of a convex polytope, Mathematika, 17, 179-184 (1970) · Zbl 0217.46703 |
| [60] | Molina-Fructuoso, M., Murray, R.: Eikonal depth: an optimal control approach to statistical depths, In preparation (2021) |
| [61] | Molina-Fructuoso, M., Murray, R.: Tukey depths and Hamilton-Jacobi differential equations, arXiv:2104.01648 (2021) · Zbl 1490.35478 |
| [62] | Oberman, AM, Wide stencil finite difference schemes for the elliptic Monge-Ampere equation and functions of the eigenvalues of the Hessian, Discrete & Continuous Dynamical Systems-B, 10, 221 (2008) · Zbl 1145.65085 |
| [63] | Piret, C., The orthogonal gradients method: A radial basis functions method for solving partial differential equations on arbitrary surfaces, J. Comput. Phys., 231, 4662-4675 (2012) · Zbl 1248.35009 |
| [64] | Piret, C., Dunn, J.: Fast rbf ogr for solving pdes on arbitrary surfaces. In: AIP Conference Proceedings, vol. 1776, AIP Publishing LLC, pp. 070005 (2016) |
| [65] | Qiao, W.; Polonik, W., Nonparametric confidence regions for level sets: statistical properties and geometry, Electron. J Stat., 13, 985-1030 (2019) · Zbl 1418.62144 |
| [66] | Qiu, B.-Z., Yue, F., Shen, J.-Y.: Brim: An efficient boundary points detecting algorithm, in Advances in Knowledge Discovery and Data Mining, Zhou, Z.-H., Li,H., Yang, Q. (eds.) Berlin, Heidelberg, Springer Berlin Heidelberg, pp. 761-768 (2007) |
| [67] | Rodríguez Casal, A., Set estimation under convexity type assumptions, Annales de l’I.H.P. Probabilités et statistiques, 43, 763-774 (2007) · Zbl 1169.62317 |
| [68] | Sethian, JA; Vladimirsky, A., Fast methods for the eikonal and related Hamilton-Jacobi equations on unstructured meshes, Proc. Natl. Acad. Sci., 97, 5699-5703 (2000) · Zbl 0963.65076 |
| [69] | Shi, Z., Enforce the Dirichlet boundary condition by volume constraint in point integral method, Commun. Math. Sci., 15, 1743-1769 (2017) · Zbl 1397.65235 |
| [70] | Small, C. G.: Multidimensional medians arising from geodesics on graphs, The Annals of Statistics, pp. 478-494 (1997) · Zbl 0923.62070 |
| [71] | Suchde, P.; Kuhnert, J., A fully lagrangian meshfree framework for pdes on evolving surfaces, J. Comput. Phys., 395, 38-59 (2019) · Zbl 1452.65178 |
| [72] | Suchde, P.; Kuhnert, J., A meshfree generalized finite difference method for surface pdes, Comput. Math. Appl., 78, 2789-2805 (2019) · Zbl 1443.65287 |
| [73] | The MathWorks Inc., alphashape: Matlab documentation. https://www.mathworks.com/help/matlab/ref/alphashape.html. Accessed: 2021-10-17 |
| [74] | Wu, H. tieng, Wu, N.: When locally linear embedding hits boundary, arXiv:1811.04423 (2019) |
| [75] | Trask, N.; Kuberry, P., Compatible meshfree discretization of surface pdes, Comput. Part. Mech., 7, 271-277 (2020) |
| [76] | Tukey, JW, Mathematics and the picturing of data, Proc. Int. Congr. Math. Vanc., 2, 1975, 523-531 (1975) · Zbl 0347.62002 |
| [77] | Vaughn, R., Berry, T., Antil, H.: Diffusion maps for embedded manifolds with boundary with applications to pdes, arXiv preprint arXiv:1912.01391 (2019) |
| [78] | Wang, M.; Leung, S.; Zhao, H., Modified virtual grid difference for discretizing the Laplace-Beltrami operator on point clouds, SIAM J. Sci. Comput., 40, A1-A21 (2018) · Zbl 1379.65083 |
| [79] | Xiao, H., Rasul, K., Vollgraf, R.: Fashion-MNIST: A novel image dataset for benchmarking machine learning algorithms, arXiv:1708.07747 (2017) |
| [80] | Yuan, A., Calder, J., Osting, B.: A continuum limit for the pagerank algorithm, European Journal of Applied Mathematics, pp. 1-33 (2020) |
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.
