Asymptotics for the length of a minimal triangulation on a random sample. (English) Zbl 0931.68046

Summary: Given \(F\subset [0,1]^2\) and finite, let \(\sigma(F)\) denote the length of the minimal Steiner triangulation of points in \(F\). By showing that minimal Steiner triangulations fit into the theory of subadditive and superadditive Euclidean functionals, we prove under a mild regularity condition that \[ \lim_{n\to\infty} \sigma(X_1,\dots, X_n)/n^{1/2}= \beta \int_{[0,1]^2} f(x)^{1/2} dx\quad\text{c.c.}, \] where \(X_1,\dots, X_n\) are i.i.d. random variables with values in \([0,1]^2\), \(\beta\) is a positive constant, \(f\) is the density of the absolutely continuous part of the law of \(X_1\), and c.c. denotes complete convergence. This extends the work of Steele. The result extends naturally to dimension three and describes the asymptotics for the probabilistic Plateau functional, thus making progress on a question of Beardwood, Halton and Hammersley. Rates of convergence are also found.


68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI


[1] BEARDWOOD, J., HALTON, J. H. and HAMMERSLEY, J. J. 1959. The shortest path through many points. Math. Proc. Cambridge Philos. Soc. 55 299 327. Z. · Zbl 0118.35601
[2] BERN, M. and EPPSTEIN, D. 1992. Mesh generation and optimal triangulation. In Computing in Z. Euclidean Geometry F. R. Hwang and D.-Z. Du, eds. World Scientific, Singapore. Z.
[3] COURANT, R. and SCHIFFER, M. 1950. Dirichlet Principle, Conformal Mapping, and Minimal Surfaces. Interscience, New York. Z. DOUGLAS. J. 1939. Minimal surfaces of higher topological structure. Ann. of Math. 40 205 298. Z.
[4] PREPARATA, F. P. and SHAMOS, M. I. 1985. Computational Geometry. Springer, New York. Z. · Zbl 0575.68059
[5] REDMOND, C. and YUKICH, J. E. 1994. Limit theorems and rates of convergence for subadditive Euclidean functionals. Ann. Appl. Probab. 4 1057 1073. Z. · Zbl 0812.60033
[6] REDMOND, C. and YUKICH, J. E. 1996. Asy mptotics for Euclidean functionals with powerweighted edges. Stochastic Process. Appl. 61 289 304. Z. · Zbl 0849.60030
[7] RHEE, W. S. 1993. A matching problem and subadditive Euclidean functionals. Ann. Appl. Probab. 3 794 801. Z. · Zbl 0784.60020
[8] SALZBERG, S., DELCHER, A., HEATH, D. and KASIF, S. 1991. Learning with a helpful teacher. In Proceedings of the 12th International Joint Conference on Artificial Intelligence. Z. · Zbl 0748.68065
[9] STEELE, J. M. 1981. Subadditive Euclidean functionals and non-linear growth in geometric probability. Ann. Probab. 9 365 376. Z. · Zbl 0461.60029
[10] STEELE, J. M. 1982. Optimal triangulation of random samples in the plane. Ann. Probab. 10 548 553. Z. · Zbl 0486.60015
[11] STEELE, J. M. 1997. Probability Theory and Combinatorial Optimization. SIAM, Philadelphia. Z. · Zbl 0916.90233
[12] YUKICH, J. E. 1995. Asy mptotics for the stochastic TSP with power weighted edges. Probab. Theory Related Fields 203 220. Z. · Zbl 0821.60023
[13] YUKICH, J. E. 1998. Probability Theory of Classical Euclidean Optimization Problems. Lecture Notes in Math. 1675. Springer, Berlin. · Zbl 0902.60001
[14] BETHLEHEM, PENNSy LVANIA 18015 E-MAIL: jey 0@lehigh.edu
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.