×

Numerical stability of a convex hull algorithm for simple polygons. (English) Zbl 0783.68132

Summary: A numerically stable and optimal \(O(n)\)-time implementation of an algorithm for finding the convex hull of a simple polygon is presented. Stability is understood in the sense of a backward error analysis. A concept of the condition number of simple polygons and its impact on the performance of the algorithm is discussed. It is shown that if the condition number does not exceed \(\bigl( 1+O( \varepsilon) \bigr) /(3 \varepsilon)\), then, in floating-point arithmetic with the unit roundoff \(\varepsilon\), the algorithm produces the vertices of a convex hull for slightly perturbed input points. The relative perturbation does not exceed \(3\varepsilon \bigl( 1+O( \varepsilon) \bigr)\).

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] B. K. Bhattacharya and H. ElGindy, A new linear convex hull algorithm for simple polygon,IEEE Transactions on Information Theory,30, 85–88, 1984. · Zbl 0531.68023 · doi:10.1109/TIT.1984.1056845
[2] H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, New York, 1987. · Zbl 0634.52001
[3] S. Fortune, Stable maintenance of point-set triangulations in two dimension,Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pp. 494–499, 1989.
[4] R. L. Graham, An efficient algorithm for determining the convex hull of a finite planar set,Information Processing Letters,1, 132–133, 1972. · Zbl 0236.68013 · doi:10.1016/0020-0190(72)90045-2
[5] R. L. Graham and F. F. Yao, Finding the convex hull of a simple polygon,Journal of Algorithms,4(4), 324–331, 1983. · Zbl 0532.68072 · doi:10.1016/0196-6774(83)90013-5
[6] L. Guibas, D. Salesin, and J. Stolfi, Epsilon geometry: building robust algorithms from imprecise computations,Proceedings of the 5th Annual ACM Symposium on Computational Geometry, pp. 208–217, 1989.
[7] L. Guibas, D. Salesin, and J. Stolfi, Constructing strongly convex approximate hulls with inaccurate primitives,Proceedings of the International Symposium SIGAL ’90, Lecture Notes in Computer Science, Vol. 450, Springer-Verlag, Berlin, pp. 261–270, 1990. · Zbl 0797.68158
[8] D. T. Lee, On finding the convex hull of a simple polygon,International Journal on Computing and Information Sciences,12(2), 87–98, 1983. · Zbl 0543.52002 · doi:10.1007/BF00993195
[9] Z. Li and V. Milenkovic, Constructing strongly convex hulls using exact and rounded arithmetic,Proceedings of the 6th Annual ACM Symposium on Computational Geometry, pp. 235–245, 1990.
[10] D. McCallum and D. Avis, A linear time algorithm for finding the convex hull of a simple polygon,Information Processing Letters,9, 201–206, 1979. · Zbl 0423.68031 · doi:10.1016/0020-0190(79)90069-3
[11] A. A. Melkman, On line construction of the convex hull of a simple polyline,Information Processing Letters,25, 11–12, 1987. · Zbl 0653.68028 · doi:10.1016/0020-0190(87)90086-X
[12] F. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985. · Zbl 0575.68059
[13] S. Y. Shin and T. C. Woo, Finding the convex hull of a simple polygon in linear time,Pattern Recognition,13, 453–458, 1986. · Zbl 0633.68088 · doi:10.1016/0031-3203(86)90043-9
[14] G. T. Toussaint, A counter-example to a convex hull algorithm for polygons,Pattern Recognition,24, 183–184, 1991. · doi:10.1016/0031-3203(91)90087-L
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.