×

zbMATH — the first resource for mathematics

Fast linear expected-time algorithms for computing maxima and convex hulls. (English) Zbl 0766.68132
Summary: This paper examines the expected complexity of boundary problems on a set of \(N\) points in \(K\)-space. We assume that the points are chosen from a probability distribution in which each component of a point is chosen independently of all other components. We present an algorithm to find the maximal points using \(KN+O(n^{1-1/K}\log^{1/K}N)\) expected scalar comparisons, for fixed \(K\geq 2\). A lower bound shows that the algorithm is optimal in the leading term. We describe a simple maxima algorithm that is easy to code, and present experimental evidence that it has similar running time. For fixed \(K\geq 2\), an algorithm computes the convex hull of the set in \(2KN+O(N^{1-1/K}N)\) expected scalar comparisons. The history of the algorithms exhibits interesting interactions among consulting, algorithm design, data analysis, and mathematical analysis of algorithms.

MSC:
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Becker, R. A., L. Denby, R. McGill, and A. R. Wilks, Analysis of data from the Places Rated Almanac,The American Statistician,41(3) (1987), 169-186.
[2] Bentley, J. L., Multidimensional divide-and-conquer,Communications of the Association for Computing Machinery,23(4) (1980), 214-229. · Zbl 0434.68049
[3] Bentley, J. L., and M. I. Shamos, Divide and conquer for linear expected time,Information Processing Letters,7(2) (1978), 87-91. · Zbl 0404.68046
[4] Bentley. J. L., H. T. Kung, M. Schkolnick, and C. D. Thompson, On the average number of maxima in a set of vectors and applications,Journal of the Association for Computing Machinery,25(4) (1978), 536-543. · Zbl 0388.68056
[5] Bentley, J. L., B. W., Weide, and A. C. Yao, Optimal exptected-time algorithms for closest point problems,ACM Transactions on Mathematical Software,6(4) (1986), 563-580. · Zbl 0441.68077
[6] Boyer, R., and D. Savageau,Places Related Almanac (Revised Edition), Rand McNally, 1985.
[7] Clarkson, K. L., and P. W. Shor, Applications of random sampling in computational geometry, II,Discrete and Computational Geometry,4(5) (1989), 387-421. · Zbl 0681.68060
[8] Devroye, L.. A note on finding convex hulls via maximal vectors,Information Processing Letters,11(1) (1980), 53-56. · Zbl 0444.68063
[9] Floyd, R. W., and R. L. Rivest, Expected time bounds for selection,Communications of the ACM,18(9) (1975), 165-172. · Zbl 0296.68049
[10] Golin, M., and R. Sedgewick, Analysis of a simple yet efficient convex hull algorithm,Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988, pp. 153-163.
[11] Graham, R. L., An efficient algorithm for determining the convex hull of a finite planar point set,Information Processing Letters,1 (1972), 132-133. · Zbl 0236.68013
[12] Kung, H. T., F. Luccio, and F. P. Preparata, On finding the maxima of a set of vectors,Journal of the Association for Computing Machinery,22(4) (1975), 469-476. · Zbl 0316.68030
[13] Monier, L., Combinatorial solutions of multidimensional divide-and-conquer recurrences,Journal of Algorithms,1(1) (1980), 60-74. · Zbl 0435.68032
[14] Preparata, F. P., and S. J. Hong, Convex hulls of finite sets of points in two and three dimensions,Communications of the Association for Computing Machinery,20(2) (1977), 87-93. · Zbl 0342.68030
[15] Preparata, F. P., and M. I. Shamos,Computational Geometry, Springer-Verlag, 1985. · Zbl 0575.68059
[16] Seidel, R., A convex hull algorithm optimal for points in even dimensions, M.Sc. Thesis, Technical Report 81-14, Department of Computer Science, University of British Columbia, Vancouver, 1981.
[17] Urgel, J., Private communication, Harvard Business School, April?May 1989.
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.