摘要: The problem of finding the convex hull intersection points random lines was studied in Devroye and Toussaint, 1993 Langerman, Golin Steiger, 2002, algorithms with expected linear time were found. We improve previous results model by giving a universal algorithm for wider range distributions.
dmtcs.org
episciences.org 参考文章(12)
Mikhail J Atallah, Computing the convex hull of line intersections Journal of Algorithms. ,vol. 7, pp. 285- 288 ,(1986) , 10.1016/0196-6774(86)90010-6
David G. Kirkpatrick, Raimund Seidel, The ultimate planar convex hull algorithm SIAM Journal on Computing. ,vol. 15, pp. 287- 299 ,(1986) , 10.1137/0215021
R.A. Jarvis, On the identification of the convex hull of a finite set of points in the plane Information Processing Letters. ,vol. 2, pp. 18- 21 ,(1973) , 10.1016/0020-0190(73)90020-3
Michael I. Shamos, Franco P. Preparata, Computational Geometry: An Introduction ,(1978)
Avraham A. Melkman, On-line construction of the convex hull of a simple polyline Information Processing Letters. ,vol. 25, pp. 11- 12 ,(1987) , 10.1016/0020-0190(87)90086-X
R.L. Graham, An efficient algorith for determining the convex hull of a finite planar set Information Processing Letters. ,vol. 1, pp. 132- 133 ,(1972) , 10.1016/0020-0190(72)90045-2
Y.T. Ching, D.T. Lee, Finding the diameter of a set of lines Pattern Recognition. ,vol. 18, pp. 249- 255 ,(1985) , 10.1016/0031-3203(85)90050-0
L. Devroye, G. Toussaint, Convex hulls for random lines Journal of Algorithms. ,vol. 14, pp. 381- 394 ,(1993) , 10.1006/JAGM.1993.1020
T. M. Chan, Optimal output-sensitive convex hull algorithms in two and three dimensions Discrete & Computational Geometry. ,vol. 16, pp. 361- 368 ,(1996) , 10.1007/BF02712873
Stefan Langerman, Mordecai Golin, William W. Steiger, The convex hull for random lines in the plane Lecture Notes in Computer Science. ,vol. 2866, pp. 172- 175 ,(2003)