Andrew Chi-Chih Yao
- 1 Avis, D. On the complexity of finding the convex hull of a set of points. Tech. Rep. SOCS 79.2, McGdl Umverslty, Montreal, Ontano, Canada, 1979Google Scholar
- 2 GRAHAM, R L An efficient algorithm for determining the convex hull of a t'mite set. Inf. Proc. Lea. 1 (1972), 132-133.Google Scholar
- 3 SHAMOS, M.I. Computational geometry. Tech. Pep., Computer Science Dep., Carnegie-Mellon Umv., Pmsburgh, Pa, May 1978.Google Scholar
- 4 VAN EMDE BOAS, P. On the f~(n log n) lower bound for convex hull and maxtmal vector determination. Inf. Proc. Left. 10 (1980), 132-136.Google Scholar
- 5 YAO, A C A lower bound to finding convex hulls. Tech Rep. STAN-CS-79-733, Computer Science Dep., Stanford, Univ., Stanford, Cahf., Apnl 1979. Google Scholar
Index Terms
- A Lower Bound to Finding Convex Hulls
Recommendations
The quickhull algorithm for convex hulls
The convex hull of a set of points is the smallest convex set that contains the points. This article presents a practical convex hull algorithm that combines the two-dimensional Quickhull algorithm with the general-dimension Beneath-Beyond Algorithm. It ...
Convex hulls of spheres and convex hulls of disjoint convex polytopes
Given a set @S of spheres in E^d, with d>=3 and d odd, having a constant number of m distinct radii @r"1,@r"2,...,@r"m, we show that the worst-case combinatorial complexity of the convex hull of @S is @Q(@__ __"1"=<"i"<>"j"=<"mn"in"j^@__ __^d^2^@__ __), ...
Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometryGiven a set Σ of spheres in Ed, with d≥3 and d odd, having a fixed number of m distinct radii ρ1,ρ2,...,ρm, we show that the worst-case combinatorial complexity of the convex hull CHd(Σ) of Σ is Θ(Σ{1≤i≠j≤m}ninj⌊ d/2 ⌋), where ni is the number of ...
Comments