Years and Authors of Summarized Original Work
-
1972; Graham
-
1973; Jarvis
-
1977; Preparata, Hong
-
1996; Chan
Problem Definition
The convex hull of a set P of n points in ℝd is the intersection of all convex regions that contain P. While convex hulls are defined for arbitrary d, the focus here is on d = 2 (and d = 3). For a more general overview, we recommend reading [7, 9] as well as [3].
A frequently used visual description for a convex hull in 2D is a rubber band: when we imagine the points in the plane to be nails and put a rubber band around them, the convex hull is exactly the structure we obtain by a tight rubber band; see Fig. 1.
The convex hull of a set of points in ℝ2
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
CGAL (2014) Computational geometry algorithms library. http://www.cgal.org
Chan T (1996) Optimal output-sensitive convex hull algorithms in two and three dimensions. Discret Comput Geom 16(4):361–368. doi:10.1007/BF02712873
Devadoss SL, O’Rourke J (2011) Discrete and computational geometry. Princeton University Press, Princeton
Graham RL (1972) An efficient algorithm for determining the convex hull of a finite planar set. Inf Process Lett 1(4):132–133
Jarvis R (1973) On the identification of the convex hull of a finite set of points in the plane. Information Process Lett 2(1):18–21. doi:10.1016/0020-0190(73)90020-3
Kettner L, Mehlhorn K, Pion S, Schirra S, Yap CK (2004) Classroom examples of robustness problems in geometric computations. In: Proceedings of the 12th annual European symposium on algorithms, vol 3221, pp 702–713
O’Rourke J (1998) Computational geometry in C, 2nd edn. Cambridge University Press, New York
Preparata FP, Hong SJ (1977) Convex hulls of finite sets of points in two and three dimensions. Commun ACM 20(2):87–93
Sack JR, Urrutia J (eds) (2000) Handbook of computational geometry. North-Holland, Amsterdam
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer Science+Business Media New York
About this entry
Cite this entry
Hemmer, M., Schmidt, C. (2016). Convex Hulls. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-2864-4_508
Download citation
DOI: https://doi.org/10.1007/978-1-4939-2864-4_508
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4939-2863-7
Online ISBN: 978-1-4939-2864-4
eBook Packages: Computer ScienceReference Module Computer Science and Engineering