×
Bentley, Jon Louis; Shamos, Michael Ian

Divide and conquer for linear expected time. (English) Zbl 0404.68046

Inf. Process. Lett. 7, 87-91 (1978).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0404.68046

Cited in 41 Documents

MSC:

68W99 Algorithms in computer science
68Q25 Analysis of algorithms and problem complexity
90C05 Linear programming

Keywords:

Divide-And-Conquer Technique; Designing Fast Algorithms; Worst-Case Time Complexity; Average-Case Algorithms; Computational Geometry; Convex Null; Linear Programming

Software:

Quicksort
Cite Review PDF
Full Text: DOI

References:

[1] Carnal, H., Die konvexe Hülle von \(n\) rotationssymmetrische verteilten Punkten, Z. Wahrscheinlichkeits, 15, 168-176 (1970) · Zbl 0193.46602
[2] Eddy, W., A new convex hull algorithm for planar sets, ACM Transactions on Mathematical Software (1977), to appear. · Zbl 0374.68036
[3] Efron, B., The convex hull of a random set of points, Biometrika, 52, 331-344 (1965) · Zbl 0138.41301
[4] Graham, R. L., An efficient algorithm for determining the convex hull of a planar set, Information Processing Lett., 1, 132-133 (1972) · Zbl 0236.68013
[5] Jarvis, R. A., On the identification of the convex hull of a finite set of points in the plane, Information Processing Lett., 2, 18-21 (1973) · Zbl 0256.68041
[6] Kendall, M. G.; Moran, P. A.P., Geometrical Probability, 125 (1963), Griffin · Zbl 0105.35002
[7] H.T. Kung, M. Schkomick and C.D. Thompson, On the average number of maxima in a set of vectors, submitted for publication.; H.T. Kung, M. Schkomick and C.D. Thompson, On the average number of maxima in a set of vectors, submitted for publication.
[8] Preparata, F. P.; Hong, S. J., Convex hulls of finite sets of points in two and three dimensions, CACM, 20, 2, 87-93 (1977) · Zbl 0342.68030
[9] Raynaud, H., Sur l’enveloppe convexe des nuages des points aléatoires dans \(R_n, I\), J. Appl. Prob., 7, 35-48 (1970) · Zbl 0192.53602
[10] Rényi, A.; Sulanke, R., Über die konvexe Hülle von \(n\) zufallig gewahlten Punkten, II, Z. Wahrscheinlichkeits, 3, 138-147 (1964) · Zbl 0126.34103
[11] Rényi, A.; Sulanke, R., Zufallige konvexe Polygone in einem Ringgebeit, Z. Wahrscheinlichkeits, 9, 146-157 (1968) · Zbl 0162.49502
[12] Santaló, L. A., Integral Geometry and Geometric Probability, (Encyclopedia of Mathematics and Its Applications, v.1. (1976), Addison-Wesley: Addison-Wesley Reading, MA), 404 · Zbl 1116.53050
[13] Sedgewick, R., Quicksort, Stanford University Dept. of Comp. Sci. Tech. Rpt. STAN-CS-75-492 (May, 1975)
[14] Shamos, M. I., Geometric complexity, Proc. Seventh Annual ACM Symposium on Automata and Computability Theory, 224-233 (1975) · Zbl 0357.68046
[15] Shamos, M. I., Problems in Computational Geometry, (Computational Geometry (1977), Springer-Verlag: Springer-Verlag Berlin), Unpublished notes. To appear as
[16] Shamos, M. I.; Hoey, D., Closest-point problems, Proc. Sixteenth Annual IEEE Symposium on Foundations of Computing, 151-162 (October, 1975)
[17] Shamos, M. I.; Hoey, D., Geometric Intersection Problems, Proc. Seventeenth Annual IEEE Symposium on Foundations of Computer Science, 208-215 (October, 1976)
[18] Ziezold, H., Über die Eckenzahl zufalliger konvexer Polygone, Izv. Akad. Nauk. Armjan. SSR. Ser. Mat., 5, 296-312 (1970) · Zbl 0197.44302
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.