Jon Louis Bentley
Franco P. Preparata
- 1 Bentley, J.L. and Shamos, M.I. Divide and conquer for linear expected time. Information Processing Lett. 7, 2, (Feb. 1978), 87-91.Google Scholar
Cross Ref
- 2 Brown, K. Q. Geometric transforms for fast geometric algorithms. Ph.D. Thesis, Carnegie-Mellon University, December 1979. Carnegie-Mellon Computer Science Tech. Rept. CMU-CS-80- 101. Google ScholarDigital Library
- 3 Devroye, L. A note on finding convex hulls via maximal vectors. Information Processing Letts. 11, 1, 53-56.Google ScholarCross Ref
- 4 Graham, R.L. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Lett. 1, 132-133.Google ScholarCross Ref
- 5 Lipton, R.J. and Tarjan, R.E. Application of a planar separator theorem. 18th Syrup. Foundations of Computer Science (Oct. 1977), IEEE, pp. 162-170.Google ScholarDigital Library
- 6 Preparata, F.P. An optimal real-time algorithm for convex hulls. Comm. ACM 22, 7, (July 1979). 402-405. Google ScholarDigital Library
- 7 Preparata, F.P. and Hong, S.J. Convex hulls of finite sets in two and three dimensions. Comm. ACM 20, 2, (Feb. 1977), 87-93. Google ScholarDigital Library
- 8 Shamos, M.I. Computational geometry. Unpublished Ph.D. Thesis, Yale University (May 1978), New Haven, Connecticut. Google ScholarDigital Library
- 9 Yao, A.C. On constructing minimum spanning trees in kdimensional space and related problems. Stanford University Computer Science Department Report STAN-CS-77-642, (Dec. 1977). Google ScholarDigital Library
- 10 Yao, A. C. A lower bound to finding convex hulls. Stanford University Computer Science Department Report STAN-CS-79-733, (April 1979). Google ScholarDigital Library
Index Terms
- Approximation algorithms for convex hulls
Recommendations
Inclusion---Exclusion Principles for Convex Hulls and the Euler Relation
Consider n points $$X_1,\ldots ,X_n$$X1,ź,Xn in $$\mathbb {R}^d$$Rd and denote their convex hull by $${\Pi }$$ź. We prove a number of inclusion---exclusion identities for the system of convex hulls $${\Pi }_I:=\mathrm{conv}(X_i: i\in I)$$źI:=conv(Xi:iźI)...
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