- 1 GRAHAM, R.L. An efficient algorithm for determining the convex hull of a planar set. Inform. Prec. Letlers 1 (1972), 132-133.Google Scholar
- 2 J ARraS, R.A. On the identification of the convex hull of a finite set of points in the plane. Inform. Prec. Letters ~ (1973), 18-21.Google Scholar
- 3 PREPARATA, F.P., AND HONG, S.J. Convex hulls of finite planar and spatial sets of points. Report R-682, Coordinated Science Lab., U. of Illinois, Urbana, Ill., April 1975.Google Scholar
- 4 PR~PARA~A, F.P., AND HONe, S.J. Convex hulls of planar and spatial sets of points. Abstract 726-68-1, Notices AM~J 2~ (1975), A-596.Google Scholar
- 5 RAYNAUD, H. Sur l'enveloppe convexe des nuages de points aleatoires dans Ra.I.J. Appl. Prob. 7 (1970), 35-48.Google Scholar
- 6 ScowsN, R.S. Algorithm 271: Quickersort. Comm. ACM 8, 11 (1965), 669-670. Google Scholar
Index Terms
- A New Convex Hull Algorithm for Planar Sets
Recommendations
-Concave hull, a generalization of convex hull
Bounding hulls such as convex hull, -shape, -hull, concave hull, crust, etc. offer a wide variety of useful applications. In this paper, we explore another bounding hull, namely -concave hull, as a generalization of convex hull. The parameter determines ...
Dynamic Planar Convex Hull
FOCS '02: Proceedings of the 43rd Symposium on Foundations of Computer ScienceIn this paper we determine the computational complexity of the dynamic convex hull problem in the planar case. We present a data structure that maintains a finite set of n points in the plane under insertion and deletion of points in amortized O(log n) ...
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^@__ __), ...
Comments