A note on the expected time required to construct the outer layer. (English) Zbl 0572.68032
The expected time E(T) of the standard divide-and-conquer algorithm for finding the outer layer of a set of points in the plane depends upon the distribution of the points. Under the mild assumption that the points are independent random vectors and have a common bounded density with compact support, it is shown that \(E(T)=O(n)\).
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Bentley, J. L.; Kung, H. T.; Schkolnick, M.; Thompson, C. D., On the average number of maxima in a set of vectors and applications, J. ACM, 25, 536-543 (1978) · Zbl 0388.68056 |
| [2] | Bentley, J. L.; Shamos, M., Divide-and-conquer for linear expected time, Inform. Process. Lett., 7, 87-91 (1978) · Zbl 0404.68046 |
| [3] | Devroye, L., Moment inequalities for random variables in computational geometry, Comput., 20, 111-119 (1983) · Zbl 0502.60016 |
| [4] | Graham, R. L., An efficient algorithm for determining the convex hull of a planar set, Inform. Process. Lett., 1, 132-133 (1972) · Zbl 0236.68013 |
| [5] | Knuth, D. E., (The Art of Computer Programming Vol. 3: Sorting and Searching (1975), Addison-Wesley: Addison-Wesley Reading, MA) |
| [6] | Preparata, F. P.; Hong, S. J., Convex hulls of finite sets of points in two and three dimensions, Comm. ACM, 20, 87-93 (1977) · Zbl 0342.68030 |
| [7] | Shamos, M., Computational geometry, (Ph.D. Dissertation (1978), Yale University) |
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.
