7.2.2 Convex Hull Algorithms and Convexity Analysis

Ronse, C.,
A Bibliography on Digital and Computational Convexity (1961-1988),
PAMI(11), No. 2, February 1989, pp. 181-190.
IEEE Abstract. IEEE Top Reference.
WWW Version. 300+ references with some annotation. BibRef 8902

Jarvis, R.A.,
On the Identification of the Convex Hull of a Finite Set of Points in the Plane,
IPL(2), 1973, pp. 18-21. BibRef 7300

Jarvis, R.A.,
Computing the Shape Hull of Points in the Plane,
PRIP77(231-241). BibRef 7700

Rutovitz, D.,
An Algorithm for In-Line Generation of a Convex Cover,
CGIP(4), No. 1, 1975, pp. 74-78. BibRef 7500

Eddy, W.F.,
A New convex Hull Algorithm for Planar Sets,
TMS(3), 1977, pp. 393-403. BibRef 7700

Anderson, K.R.,
A Reevaluation of an Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set,
IPL(7), 1978, pp. 53-55. BibRef 7800

Koplowitz, J., Jouppi, D.,
A More Efficient Convex Hull Algorithm,
IPL(7), 1978, pp. 56-57. BibRef 7800

Akl, S.G., Toussaint, G.T.,
A Fast Convex Hull Algorithm,
IPL(7), 1978, pp. 219-222. BibRef 7800
And:
Efficient Convex Hull Algorithms for Pattern Recognition Applications,
ICPR78(483-487). BibRef

Devroye, L., Toussaint, G.T.,
A Note on Linear Expected Time Algorithms for Finding Convex Hulls,
Computing(26), 1981, pp. 361-366. BibRef 8100

Toussaint, G.T.,
A Simple Proof of Pach's Extremal Theorem for Convex Polygons,
PRL(1), 1982, pp. 85-86. See also Single Linear Algorithm for Intersecting Convex Polygons, A. BibRef 8200

Bhattacharya, B.K., Toussaint, G.T.,
Time- and Storage-Efficient Implementations of an Optimal Planar Convex Hull Algorithm,
IVC(1), No. 3, August 1983, pp. 140-144.
WWW Version. BibRef 8308

Toussaint, G.T.,
A Historical Note on Convex Hull Finding Algorithms,
PRL(3), 1985, pp. 21-28. BibRef 8500

McQueen, M.M., Toussaint, G.T.,
On the Ultimate Convex Hull Algorithm in Practice,
PRL(3), 1985, pp. 29-34. BibRef 8500

Toussaint, G.T.,
On the Application of the Convex Hull to Histogram Analysis in Threshold Selection,
PRL(2), 1983, pp. 75-77. BibRef 8300

Toussaint, G.T., Avis, D.,
On A Convex Hull Algorithm for Polygons and Its Application to Triangulation Problems,
PR(15), No. 1, 1982, pp. 23-29.
WWW Version. BibRef 8200

Toussaint, G.T., El Gindy, H.,
A Counterexample to an Algorithm for Computing Monotone Hulls of Simple Polygons,
PRL(1), 1983, pp. 219-222. BibRef 8300

Toussaint, G.T.,
Complexity, Convexity, And Unimodality,
CIS(13), 1984, pp. 197-217. BibRef 8400

Akl, S.G.,
A Constant-Time Parallel Algorithm for Computing Convex Hulls,
BIT(22), 1982, pp. 130-134. BibRef 8200

Kim, C.E., Sklansky, J.,
Digital and Cellular Convexity,
PR(15), No. 5, 1982, pp. 359-367.
WWW Version. BibRef 8200

Kim, C.E.,
On the Cellular Convexity of Complexes,
PAMI(3), No. 6, November 1981, pp. 617-625. BibRef 8111

Kim, C.E., and Rosenfeld, A.,
Digital Straight Lines and Convexity of Digital Regions,
PAMI(4), No. 2, March 1982, pp. 149-153. BibRef 8203
Earlier:
On the Convexity of Digital Regions,
ICPR80(1010-1015). See also Digital Straight Line Segments. BibRef

Kim, C.E., and Rosenfeld, A.,
Convex Digital Solids,
PAMI(4), No. 6, November 1982, pp. 612-618. BibRef 8211

Kim, C.E.,
Digital Convexity, Straightness, and Convex Polygons,
PAMI(4), No. 6, November 1982, pp. 618-626. BibRef 8211

Bykat, A.,
Convex Hull of a Finite Set of Points in Two Dimensions,
IPL(7), 1978, pp. 296-298. BibRef 7800

Zucker, S.W., Hummel, R.A.,
Toward a Low-Level Description of Dot Clusters: Labeling Edge, Interior, and Noise Points,
CGIP(9), 1979, pp. 213-233. BibRef 7900

Green, P.J.,
Constructing the Convex Hull of a Set of Points in the Plane,
Computer Journal(22), 1979, pp. 262-266. BibRef 7900

Aki, S.G.,
Two Remarks on a Convex Hull Algorithm,
IPL(8), 1979, pp. 108-109. BibRef 7900

Fournier, A.,
Comments on Convex Hull of a Finite Set of Points in Two Dimensions,
IPL(8), 1979, pp. 173. BibRef 7900

Avis, D.,
Comments on a Lower Bound for Convex Hull Determination,
IPL(11), 1980, pp. 126. See also On the O(n log n) Lower Bound for Convex Hull and Maximal Vector Determination. BibRef 8000

Andrew, A.M.,
Another Efficient Algorithm for Convex Hulls in Two Dimensions,
IPL(9), 1979, pp. 216-219. BibRef 7900

Boas, P.v.E.,
On the O(n log n) Lower Bound for Convex Hull and Maximal Vector Determination,
IPL(10), 1980, pp. 132-136. See also Comments on a Lower Bound for Convex Hull Determination. BibRef 8000

Overmars, M.H., van Leeuwen, J.,
Further comments on Bykat's Convex Hull Algorithm,
IPL(10), 1980, pp. 209-212. See also Convex Hull of a Finite Set of Points in Two Dimensions. BibRef 8000

Devroye, L.,
A Note on Finding Convex Hulls via Maximal Vectors,
IPL(11), 1980, pp. 53-56. BibRef 8000

Janos, L., Rosenfeld, A.,
Some Results on Fuzzy (Digital) Convexity,
PR(15), No. 5, 1982, pp. 379-382.
WWW Version. BibRef 8200

Gaafar, M.,
Convexity Verification, Block-Chords, and Digital Straight Lines,
CGIP(6), August 1977, pp. 361-370. BibRef 7708

Preparata, F.P., Hong, S.J.,
Convex Hulls of Finite Sets of Points in Two and Three Dimensions,
CACM(20), No. 1, January 1977, pp. 87-93. BibRef 7701

Preparata, F.P.,
An Optimal Real-Time Algorithm for Planar Convex Hulls,
CACM(22), 1979, pp. 402-405. BibRef 7900

Bentley, J.L., Faust, M.G., Preparata, F.P.,
Approximation Algorithms for Convex Hulls,
CACM(25), No. 1, January 1982, pp. 64-68. BibRef 8201

Medek, V.,
On the Boundary of a Finite Set of Points in the Plane,
CGIP(15), No. 1, January 1981, pp. 93-99.
WWW Version. BibRef 8101

Yao, A.C.C.,
A Lower Bound to Finding Convex Hulls,
JACM(28), 1981, pp. 780-787. BibRef 8100

Vaishnavi, V.K.,
Computing Point Enclosures,
TC(31), No. 1, 1982, pp. 22-29. BibRef 8200

Klette, R.[Reinhard],
On the Approximation of Convex Hulls of Finite Grid Point Sets,
PRL(2), No. 1, 1983, pp. 19-22. BibRef 8300

Klette, R.[Reinhard],
The M-Dimensional Grid Point Space,
CVGIP(30), No. 1, April 1985, pp. 1-12.
WWW Version. BibRef 8504

Chassery, J.M.,
Discrete Convexity: Definition, Parameterization, and Compatibility with Continuous Convexity,
CVGIP(21), 1983, pp. 326-344. BibRef 8300

Allison, D.C., Noga, M.T.,
Some Performance Tests of Convex Hull Algorithms,
BIT(24), 1984, pp. 2-13. BibRef 8400

Soisalon-Soininen, E.,
On Computing Approximate Convex Hulls,
IPL(16), 1983, pp. 121-126. BibRef 8300

Johansen, G.H.[Gunner Helweg], Gram, C.,
A Simple Algorithm for Building the 3-D Convex Hull,
BIT(23), No. 2, 1983, pp. 146-160. BibRef 8300

Jozwik, A.,
A Method for Solving the N-Dimensional Convex Hull Problem,
PRL(2), 1983, pp. 23-25. BibRef 8300

Handley, C.C.,
Efficient Planar Convex Hull Algorithm,
IVC(3), No. 1, February 1985, pp. 29-35.
WWW Version. BibRef 8502

Chazelle, B.,
On the Convex Layers of a Planar Set,
IT(31), 1985, pp. 509-517. BibRef 8500

Ronse, C.,
A Strong Chord Property for 4-Connected Convex Digital Sets,
CVGIP(35), No. 2, August 1986, pp. 259-269. BibRef 8608

Bailey, T., and Cowles, J.,
A Convex Hull Inclusion Test,
PAMI(9), No. 2, March 1987, pp. 312-316. BibRef 8703

Prince, J.L., and Willsky, A.S.,
Reconstructing Convex Sets from Support Line Measurements,
PAMI(12), No. 4, April 1990, pp. 377-389.
IEEE Abstract. IEEE Top Reference.
WWW Version. For computed tomography. BibRef 9004

Shan, L.Y.[Liu-Yu], Thonnat, M.,
Description Of Object Shapes By Apparent Boundary And Convex Hull,
PR(26), No. 1, January 1993, pp. 95-107.
WWW Version. BibRef 9301
Earlier:
Using apparent boundary and convex hull for the shape characterization of foraminifera images,
ICPR92(III:569-572).
WWW Version. 9008 BibRef

Wu, X.L.[Xiao-Lin], and Ronke, J.,
On Properties of Discretized Convex Curves,
PAMI(11), No. 2, February 1989, pp. 217-223.
IEEE Abstract. IEEE Top Reference.
WWW Version. BibRef 8902

Ye, Q.Z.,
A Fast Algorithm for Convex-Hull Extraction in 2D Images,
PRL(16), No. 5, May 1995, pp. 531-537. BibRef 9505

Wright, M., Fitzgibbon, A.W., Giblin, P.J., Fisher, R.B.,
Convex Hulls, Occluding Contours, Aspect Graphs and the Hough Transform,
IVC(14), No. 8, August 1996, pp. 627-634.
WWW Version. 9609 BibRef
Earlier:
Beyond the Hough Transform: Further Properties of the R-Theta Mapping and Their Applications,
ORCV96(361) 9611 BibRef Edinburgh BibRef

Lindenbaum, M., Bruckstein, A.M.,
Reconstructing a Convex Polygon from Binary Perspective Projections,
PR(23), No. 12, 1990, pp. 1343-1350.
WWW Version. BibRef 9000

Lindenbaum, M.[Michael], and Bruckstein, A.M.[Alfred M.],
Blind Approximation of Planar Convex Sets,
RA(10), 1994, pp. 517-529. BibRef 9400
And:
Blind Approximation of Planar Convex Shapes,
MDSG94(415-422) BibRef

Barber, C.B., Dobkin, D.P., Huhdanpaa, H.,
The Quickhull Algorithm for Convex Hulls,
TMS(22), No. 4, December 1996, pp. 469-483. 9701 BibRef

Tzionas, P., Thanailakis, A., Tsalides, P.,
An Efficient Algorithm for the Largest Empty Figure Problem-Based on a 2D Cellular-Automaton Architecture,
IVC(15), No. 1, January 1997, pp. 35-45.
WWW Version. 9702 BibRef

Gofman, Y.,
Outline of a Set of Points,
PRL(14), 1993, pp. 31-38. BibRef 9300

Chaudhuri, B.B.,
Fuzzy Convex Hull Determination in 2-D Space,
PRL(12), 1991, pp. 591-594. BibRef 9100

Hussein, Z.,
A Fast Approximation to a Convex Hull,
PRL(8), 1988, pp. 289-294. BibRef 8800

Melter, R.A.,
Convexity Is Necessary: A Correction,
PRL(8), 1988, pp. 59. BibRef 8800

Inselberg, A., Chomut, T., Reif, M.,
Convexity Algorithms in Parallel Coordinates,
JACM(34), 1987, pp. 765-801. BibRef 8700

Latecki, L.J., Rosenfeld, A., Silverman, R.,
Generalized Convexity: C3 and Boundaries of Convex-Sets,
PR(28), No. 8, August 1995, pp. 1191-1199.
WWW Version. BibRef 9508

Zimmer, Y., Tepper, R., Akselrod, S.,
An Improved Method to Compute the Convex-Hull of a Shape in a Binary Image,
PR(30), No. 3, March 1997, pp. 397-402.
WWW Version. 9705 BibRef

Mandal, D.P., Murthy, C.A.,
Selection of Alpha for Alpha Hull in R-2,
PR(30), No. 10, October 1997, pp. 1759-1767.
WWW Version. 9712 BibRef

Lin, J.C., Lin, J.Y.,
A 1 Logn Parallel Algorithm for Detecting Convex Hulls on Image Boards,
IP(7), No. 6, June 1998, pp. 922-925.
WWW Version. 9806 BibRef

Kudo, M.[Mineichi], Torii, Y.[Yoichiro], Mori, Y.[Yasukuni], Shimbo, M.[Masaru],
Approximation of Class Regions by Quasi Convex Hulls,
PRL(19), No. 9, 31 July 1998, pp. 777-786. BibRef 9807

Chaudhuri, B.B., Rosenfeld, A.,
On the computation of the digital convex hull and circular hull of a digital region,
PR(31), No. 12, December 1998, pp. 2007-2016.
WWW Version. BibRef 9812

Hall, P.[Peter], Turlach, B.A.[Berwin A.],
On the Estimation of a Convex Set with Corners,
PAMI(21), No. 3, March 1999, pp. 225-234.
IEEE Abstract. IEEE Top Reference.
WWW Version. Not really a convex hull, but a boundary composed of curves with corners. BibRef 9903

Andrefouët, S., Roux, L., Chancerelle, Y., Bonneville, A.,
A Fuzzy-Possibilistic Scheme of Study for Objects with Indeterminate Boundaries: Application to French Polynesian Reefscapes,
GeoRS(38), No. 1, January 2000, pp. 257-270.
IEEE Top Reference. 0002 BibRef

Cinque, L., di Maggio, C.,
A BSP realisation of Jarvis' algorithm,
PRL(22), No. 2, February 2001, pp. 147-155. 0101
HTML Version. BibRef
Earlier:
A BSP realisation of Jarvis's algorithm,
CIAP99(247-252).
WWW Version. 9909 See also On the Identification of the Convex Hull of a Finite Set of Points in the Plane. BibRef

Arcelli, C.[Carlo], Sanniti di Baja, G.[Gabriella], Svensson, S.[Stina],
Computing and analysing convex deficiencies to characterise 3D complex objects,
IVC(23), No. 2, 1 February 2004, pp. 203-211.
WWW Version. 0412 BibRef
Earlier: A2, A3, A1:
Finding cavities and tunnels in 3D complex objects,
CIAP03(342-347).
IEEE Abstract. IEEE Top Reference. 0310 BibRef

Ostrouchov, G., Samatova, N.F.,
On FastMap and the Convex Hull of Multivariate Data: Toward Fast and Robust Dimension Reduction,
PAMI(27), No. 8, August 2005, pp. 1340-1343.
IEEE Abstract. IEEE Top Reference. 0506 BibRef

Rahtu, E.[Esa], Salo, M.[Mikko], Heikkila, J.[Janne],
A New Convexity Measure Based on a Probabilistic Interpretation of Images,
PAMI(28), No. 9, September 2006, pp. 1501-1512.
WWW Version. 0608Generate pairs of points and measure the probability that a point dividing the line is in the set. FFT implementation is possible. See also Affine Invariant Pattern Recognition Using Multiscale Autoconvolution. BibRef

Rosin, P.L.[Paul L.], Mumford, C.L.[Christine L.],
A symmetric convexity measure,
CVIU(103), No. 2, August 2006, pp. 101-111.
WWW Version. 0608 BibRef
Earlier: ICPR04(IV: 11-14).
WWW Version. 0409Shape measure; Polygon; Convexity; Convex hull; Convex skull BibRef

Lu, K.[Kefei], Pavlidis, T.[Theo],
Detecting textured objects using convex hull,
MVA(18), No. 2, April 2007, pp. 123-133.
WWW Version. 0704 BibRef

Stahl, J.S.[Joachim S.], Wang, S.[Song],
Edge Grouping Combining Boundary and Region Information,
IP(16), No. 10, October 2007, pp. 2590-2606.
WWW Version. 0711 BibRef
Earlier:
Convex Grouping Combining Boundary and Region Information,
ICCV05(II: 946-953).
WWW Version. 0510 BibRef

Stahl, J.S.[Joachim S.], Wang, S.[Song],
Globally Optimal Grouping for Symmetric Closed Boundaries by Combining Boundary and Region Information,
PAMI(30), No. 3, March 2008, pp. 395-411.
WWW Version. 0801 Symmetry, 2-D. BibRef
Earlier:
Globally Optimal Grouping for Symmetric Boundaries,
CVPR06(I: 1030-1037).
WWW Version. 0606Bilateral symmetry of natural and artificial objects. Use symmetry to detect closed boundaries. BibRef

Brlek, S.[Srecko], Lachaud, J.O.[Jacques-Olivier], Provençal, X.,
Combinatorial View of Digital Convexity,
DGCI08(xx-yy).
WWW Version. 0804 BibRef

Schulz, H.[Henrik],
Polyhedral Surface Approximation of Non-convex Voxel Sets through the Modification of Convex Hulls,
IWCIA08(xx-yy).
WWW Version. 0804 BibRef

Biswas, A.[Arindam], Bhowmick, P.[Partha], Sarkar, M.[Moumita], Bhattacharya, B.B.[Bhargab B.],
Finding the Orthogonal Hull of a Digital Object: A Combinatorial Approach,
IWCIA08(xx-yy).
WWW Version. 0804 BibRef

Biswas, A.[Arindam], Bhowmick, P.[Partha], Bhattacharya, B.B.[Bhargab B.],
TIPS: On Finding a Tight Isothetic Polygonal Shape Covering a 2D Object,
SCIA05(930-939).
WWW Version. 0506 BibRef

Borgefors, G.[Gunilla], Strand, R.[Robin],
An Approximation of the Maximal Inscribed Convex Set of a Digital Object,
CIAP05(438-445).
WWW Version. 0509 BibRef

Röttger, S.[Stefan], Guthe, S.[Stefan], Schieber, A.[Andreas], Ertl, T.[Thomas],
Convexification of Unstructured Grids,
VMV04(283-292). 0411 BibRef

Miller, G.[Gregor], Hilton, A.[Adrian],
Exact View-Dependent Visual Hulls,
ICPR06(I: 107-111).
WWW Version. 0609 BibRef

Mavroforakis, M.E.[Michael E.], Sdralis, M.[Margaritis], Theodoridis, S.[Sergios],
A novel SVM Geometric Algorithm based on Reduced Convex Hulls,
ICPR06(II: 564-568).
WWW Version. 0609 BibRef

Kiselman, C.O.[Christer O.],
Convex Functions on Discrete Sets,
IWCIA04(443-457).
WWW Version. 0505 BibRef

Kovalevsky, V.A.[Vladimir A.], Schulz, H.[Henrik],
Convex Hulls in a 3-Dimensional Space,
IWCIA04(176-196).
WWW Version. 0505 BibRef

Erol, A.[Ali], Bebis, G.N.[George N.], Boyle, R.D.[Richard D.], Nicolescu, M.[Mircea],
Visual Hull Construction Using Adaptive Sampling,
WACV05(I: 234-241).
WWW Version. 0502 BibRef

Guan, L.[Li], Sinha, S.[Sudipta], Franco, J.S.[Jean-Sebastien], Pollefeys, M.[Marc],
Visual Hull Construction in the Presence of Partial Occlusion,
3DPVT06(413-420).
WWW Version. 0606 BibRef

Franco, J.S., Boyer, E.,
Exact polyhedral visual hulls,
BMVC03(xx-yy).
HTML Version. 0409 Code, Convex Hull.
WWW Version. BibRef

Boyer, E., Franco, J.S.,
A hybrid approach for computing visual hulls of complex objects,
CVPR03(I: 695-701).
IEEE Abstract. IEEE Top Reference. 0307Space discretization, which does not rely on a regular grid where most cells are ineffective, but rather on an irregular grid where sample points lie on the surface of the visual hull. BibRef

Brand, M., Kang, K.[Kongbin], Cooper, D.B.,
Algebraic solution for the visual hull,
CVPR04(I: 30-35).
IEEE Abstract. IEEE Top Reference. 0408 BibRef

Rosenfeld, A.[Azriel], Klette, R.[Reinhard],
Digital Straightness,
UMD-- TR4279, August 2001
WWW Version.
WWW Version.
WWW Version.
WWW Version. BibRef 0108

Yu, L.[Linjiang], Klette, R.,
An approximative calculation of relative convex hulls for surface area estimation of 3d digital objects,
ICPR02(I: 131-134).
WWW Version. 0211 BibRef

Lee, T., Atkins, M., Li, Z.N.[Ze-Nian],
Indentation and protrusion detection and its applications,
ScaleSpace01(xx-yy). 0106 BibRef

Suk, T.[Tomás], Flusser, J.[Jan],
Convex Layers: A New Tool for Recognition of Projectively Deformed Point Sets,
CAIP99(454-461).
WWW Version. 9909 BibRef
Earlier:
The features for recognition of projectively deformed point sets,
ICIP95(III: 348-351).
WWW Version. 9510 BibRef

Kakarala, R.[Ramakrishna],
Testing for Convexity with Fourier Descriptors,
ICPR98(Vol I: 792-794).
WWW Version. 9808 BibRef

Marzetta, T.L.,
Reflection coefficient representation for convex planar sets,
ICIP98(I: 607-609).
WWW Version. 9810 BibRef

Nikolova, M.,
Estimation of binary images by minimizing convex criteria,
ICIP98(II: 108-112).
WWW Version. 9810 BibRef

Albanesi, M.G., Ferretti, M., Zangrandi, L.,
A pyramidal approach to convex hull and filling algorithms,
CIAP95(139-144).
WWW Version. 9509 BibRef

Meier, R., Ackermann, F., Herrmann, G., Posch, S., Sagerer, G.,
Segmentation of molecular surfaces based on their convex hull,
ICIP95(III: 552-555).
WWW Version. 9510 BibRef

Korneenko, N.[Nickolay],
Minimum-space time-optimal convex hull algorithms (preliminary report),
CAIP93(231-236).
WWW Version. 9309 BibRef

Miller, R., Stout, Q.F.,
Convexity Algorithms for Parallel Machines,
CVPR88(918-924).
IEEE Abstract. IEEE Top Reference. See also Geometric Algorithms for Digitized Pictures on a Mesh-Connected Computer. BibRef 8800

Kobatake, H., Murakami, M.,
Adaptive Filter to Detect Rounded Convex Regions: Iris Filter,
ICPR96(II: 340-344).
WWW Version. 9608(Tokyo Univ. of Agriculture and Technology, J) BibRef

Rangarajan, A., Chellappa, R.,
Generalized graduated nonconvexity algorithm for maximum a posteriori image estimation,
ICPR90(II: 127-133).
WWW Version. 9008 BibRef

Murakami, K., Koshimizu, H., Hasegawa, K.,
An algorithm to extract convex hull on thetas Hough transform space,
ICPR88(I: 500-503).
WWW Version. 8811 BibRef

Chapter on 2-D Feature Analysis, Extraction and Representations, Shape, Skeletons, Texture continues in
Convex Hull of Polygons .