Stretch factor in a planar Poisson–Delaunay triangulation with a large intensity

Advances in Applied Probability - Tập 50 Số 01 - Trang 35-56 - 2018
Nicolas Chenavier1, Olivier Devillers2
1Université du Littoral Côte d'Opale
2Geometric Algorithms and Models Beyond the Linear and Euclidean realm

Tóm tắt

AbstractLetX:=Xn∪ {(0, 0), (1, 0)}, whereXnis a planar Poisson point process of intensityn. We provide a first nontrivial lower bound for the distance between the expected length of the shortest path between (0, 0) and (1, 0) in the Delaunay triangulation associated withXwhen the intensity ofXngoes to ∞. Simulations indicate that the correct value is about 1.04. We also prove that the expected length of the so-called upper path converges to 35 / 3π2, yielding an upper bound for the expected length of the smallest path.

Từ khóa


Tài liệu tham khảo

10.1007/3-540-51542-9_6

10.1093/acprof:oso/9780198506263.001.0001

10.1016/j.tcs.2015.12.015

10.1007/BF02187801

10.1214/aoap/1177005277

10.1016/j.comgeo.2004.02.002

Cheng, 2013, Delaunay Mesh Generation

10.1142/S0129054102001047

10.1007/978-3-540-33259-6_6

2016, J. Comput. Geom., 7, 332

10.1239/aap/1037990949

2018, Discrete Comput. Geom., 1

2004, SIAM J. Comput., 33, 937

10.1016/j.comgeo.2006.05.005

2000, Adv. Appl. Prob., 32, 1, 10.1239/aap/1013540019

10.1142/8685

10.1214/13-AAP992

Xia, 2011, Proceedings 23th Canadian Conference on Computational Geometry

10.1137/110832458

10.3150/15-BEJ732

10.1007/978-3-540-78859-1

10.1051/ps/2016012

Thông tin
Thông tin xuất bản

Advances in Applied Probability

Tập 50 Số 01

35-56

Thông tin tác giả