A Bibliography on Digital and Computational Convexity (1961-1988)

ABSTRACT

A bibliography of 370 references of books, papers in serial journals, and conference papers, on convexity in relation to computer science is presented. The subject is divided into five topics: (1) convexity and straightness in digital images; (2) convex hull algorithms and their complexity; (3) other computational problems related to convexity; (4) miscellaneous applications; and (5) general mathematical sources. These references range in time from 1961 to September 1988.

REFERENCES

• 1: {1} T. A. Anderson and C. E. Kim, "Representation of digital line segments and their preimages," <i>Comput. Vision, Graphics, Image Processing</i>, vol. 30, no. 3, pp. 279-288, June 1985.
• 2: {2} C. Arcelli and A. Massaroti, "Regular Arcs in Digital Contours," <i>Comput. Graphics Image Processing</i>, vol. 4, no. 4, pp. 339-360, Dec. 1975; Erratum, vol. 5, no. 2, p. 289, June 1976.
• 3: {3} C. Arcelli and A. Massaroti, "On the parallel generation of straight lines," <i>Comput. Graphics Image Processing</i>, vol. 7, no. 1, pp. 67-83, Feb. 1978.
• 4: {4} G. Bongiovanni, F. Luccio, and A. Zorat, "The discrete equation of the straight line," <i>IEEE Trans. Comput.</i>, vol. C-24, no. 3, pp. 310-313, Mar. 1975.
• 5: {5} R. Brons, "Linguistic methods for the description of a straight line on a grid," <i>Comput. Graphics Image Processing</i>, vol. 3, no. 1, pp. 48-62, Mar. 1974.
• 6: {6} J. M. Chassery, "Discrete convexity; Definition parametrisation and compatibility," in <i>Proc. 6th ICPR</i>, Oct. 1982, pp. 645-647.
• 7: {7} J. M. Chassery, "Discrete convexity: Definition, parametrisation, and compatibility with continuous convexity," <i>Comput. Vision, Graphics, Image Processing</i>, vol. 21, no. 3, pp. 326-344, Mar. 1983.
• 8: {8} H. U. Döhler and P. Zamperoni, "Compact contour codes for convex binary patterns," <i>Signal Processing</i>, vol. 8, no. 1, pp. 23-39, Feb. 1985.
• 9: {9} L. Dorst, "The accuracy of the digital representation of a straight line," in <i>Fundamental Algorithms for Computer Graphics</i>, R. A. Earnshaw, Ed., NATO ASI Series F, Vol. 17. Berlin: Springer-Verlag, 1985, pp. 141-152.
• 10: {10} L. Dorst and R. P. W. Duin, "Spirograph theory: A framework for calculations on digitized straight lines," <i>IEEE Trans. Pattern Anal. Machine Intell.</i>, vol. PAMI-6, no. 5, pp. 632-639, Sept. 1984.
• 11: {11} L. Dorst and A. W. M. Smeulders, "The estimation of parameters of digital straight line segments," in <i>Proc. 6th ICPR</i>, Oct. 1982, pp. 601-603.
• 12: {12} L. Dorst and A. W. M. Smeulders, "Discrete representation of straight lines," <i>IEEE Trans. Pattern Anal. Machine Intell.</i>, vol. PAMI-6, no. 4, pp. 450-463, July 1984.
• 13: L Dorst , A W M Smeulders, Best linear unbiased estimators for properties of digitized straight lines, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.2, p.276-282, March 1986 [doi>10.1109/TPAMI.1986.4767781]
• 14: {14} H. Freeman, "On the encoding of arbitrary geometric configurations," <i>IRE Trans. Electon. Comput.</i>, vol. EC-10, pp. 260-268, June 1961.
• 15: {15} H. Freeman, "Boundary encoding and processing," in <i>Picture Processing and Psychopictorics</i>, B. S. Lipkin and A. Rosenfeld. Eds. New York: Academic, 1970, pp. 241-266.
• 16: {16} H. Freeman, "Algorithm for generating a digital straight line on a triangular grid," <i>IEEE Trans. Comput.</i>, vol. C-28, no. 2, pp. 150-152, Feb. 1979.
• 17: {17} M. Gaafar, "Convexity verification, block-chords, and digital straight lines," <i>Comput. Graphics Image Processing</i>, vol. 6, no. 4, pp. 361-370, Aug. 1977.
• 18: {18} H. P. A. Haas, "Convexity analysis of hexagonally sampled images," Ph.D. dissertation, Technische Hogeschool Delft, Delft, The Netherlands, 1985.
• 19: {19} L. Hodes, "Discrete approximation of continuous convex blobs," SIAM J. Appl. Math, vol. 19, no. 2, pp. 477-485, Sept. 1970.
• 20: {20} S. H. Y. Hung, "On the straightness of digital arcs," <i>IEEE Trans. Pattern Anal. Machine Intell.</i>, vol. PAMI-7, no. 2, pp. 203-215, Mar. 1985.
• 21: {21} S. H. Y. Hung, and T. Kasvand, "On the chord property and its equivalences," in <i>Proc. 7th. ICPR</i>, July-Aug. 1984, pp. 116-119.
• 22: {22} L. Janos and A. Rosenfeld, "Some results on fuzzy (digital) convexity," <i>Pattern Recognition</i>, vol. 15, no. 5, pp. 379-382, 1982.
• 23: {23} C. E. Kim, "On the cellular convexity of complexes," <i>IEEE Trans. Pattern Anal. Machine Intell.</i>, vol. PAMI-3, no. 6, pp. 617-625, Nov. 1981 (also Subsection B.1).
• 24: {24} C. E. Kim, "On cellular straight line segments," <i>Comput. Graphics Image Processing</i>, vol. 18, no. 4, pp. 369-381, Apr. 1982.
• 25: {25} C. E. Kim, "Digital convexity, straightness and convex polygons," <i>IEEE Trans. Pattern Anal. Machine Intell.</i>, vol. PAMI-4, no. 6, pp. 618- 626, Nov. 1982.
• 26: {26} C. E. Kim, "Three-dimensional digital line segments," <i>IEEE Trans. Pattern Anl. Machine Intell.</i>, vol. PAMI-5, no. 2, pp. 231-234. Mar. 1983.
• 27: {27} C. E. Kim, "Three-dimensional digital planes," <i>IEEE Trans. Pattern Anal. Machine Intell.</i>, vol. PAMI-6, no. 5, pp. 639-645, Sept. 1984.
• 28: {28} C. E. Kim and A. Rosenfeld, "On the convexity of digital regions," in <i>Proc. 5th ICPR</i>, Dec. 1980, pp. 1010-1015.
• 29: {29} C. E. Kim and A. Rosenfeld, "Digital straight lines and convexity of digital regions," <i>IEEE Trans. Pattern Anal. Machine Intell.</i>, vol. PAMI-4, no. 2, pp. 149- 153, Mar. 1982.
• 30: {30} C. E. Kim and J. Sklansky, "Convex digital solids," <i>IEEE Trans. Pattern Anal. Machine Intell.</i>, vol. PAMI-4, no. 6. pp. 612-618, Nov. 1982.
• 31: {31} C. E. Kim and J. Sklansky, "Digital and cellular convexity," <i>Pattern Recognition</i>, vol. 15, no. 5, pp. 359-367, 1982.
• 32: {32} H. Klaasman, "Some aspects of the accuracy of the approximated position of a straight line on a grid," <i>Comput. Graphics Image Processing</i>, vol. 4, no. 3, pp. 225-235, Sept. 1975
• 33: {33} H. C. Lee and K. S. Fu, "Using the FFT to determine digital straight line chain codes," <i>Comput. Graphics Image Processing</i>, vol. 18, no. 4, pp. 359-368, Apr. 1982.
• 34: {34} X. Y. Luo and L. D. Wu, "The generalized chord property of a digital plane element," in <i>Proc. 8th ICPR</i>, Oct. 1986, pp. 1159- 1161.
• 35: {35} M. D. McIlroy, "A note on discrete representation of lines," <i>AT&T Tech. J.</i>, vol. 64, no. 2, pp. 481-490, Feb. 1984.
• 36: {36} M. Minsky and S. Papert, <i>Perceptrons</i>. Cambridge, MA: MIT Press, 1968.
• 37: G. Ugo Montanari, On Limit Properties in Digitization Schemes, Journal of the ACM (JACM), v.17 n.2, p.348-360, April 1970 [doi>10.1145/321574.321588]
• 38: Son Pham, Digital straight segments, Computer Vision, Graphics, and Image Processing, v.36 n.1, p.10-30, Oct. 1986 [doi>10.1016/S0734-189X(86)80026-3]
• 39: {39} C. Ronse, "A simple proof of Rosenfeld's characterization of digital straight line segments," <i>Pattern Recognition Lett.</i>, vol. 3, no. 5, pp. 323-326, Sept. 1985.
• 40: {40} C. Ronse, "Definitions of convexity and convex hulls in digital images," <i>Bull. Société Mathématique de Belgique</i>, vol. 37, no. 2, pp. 71-85, 1985.
• 41: {41} C. Ronse, "Criteria for approximation of linear and affine functions," <i>Arch. Math.</i>, vol. 46, pp. 371-384, 1986.
• 42: Christian Ronse, A strong chord property for 4-connected convex digital sets, Computer Vision, Graphics, and Image Processing, v.35 n.2, p.259-269, Aug. 1986 [doi>10.1016/0734-189X(86)90030-7]
• 43: {43} B. Rosenberg, "The analysis of convex blobs," <i>Comput. Graphics Image Processing</i>, vol. 1, no. 2, pp. 183-192, Aug. 1972.
• 44: {44} A. Rosenfeld. "Digital straight line segments," <i>IEEE Trans. Comput.</i>, vol. C-23, no. 2, pp. 1264-1269, Dec. 1974.
• 45: {45} A. Rosenfeld, "Measuring the sizes of concavities," <i>Pattern Recognition Lett.</i>, vol. 3, no. 1, pp. 71-75, Jan. 1985.
• 46: {46} A. Rosenfeld and C. E. Kim, "How a digital computer can tell whether a line is straight," <i>Amer. Math. Monthly</i>, vol. 89, no. 4, pp. 230-235, Apr. 1982.
• 47: {47} J. Rothstein and C. Weiman, "Parallel and sequential specification of a context sensitive language for straight lines on grids," <i>Comput. Graphics Image Processing</i>, vol. 5, no. 1, pp. 106-124, Mar. 1976.
• 48: Jean Serra, Image Analysis and Mathematical Morphology, Academic Press, Inc., Orlando, FL, 1983
• 49: {49} R. Shoucri, R. Benesch, and S. Thomas, "Note on the determination of a digital straight line from chain codes," <i>Comput. Vision. Graphics, Image Processing</i>, vol. 29, no. 1, pp. 133-139, Jan. 1983.
• 50: {50} J. Sklansky, "Recognizing convex blobs," in <i>Proc. 1st IJCAI</i>, May 1969, pp. 107-116.
• 51: {51} J. Sklansky, "Recognition of convex blobs," <i>Pattern Recognition</i>, vol. 2, no. 1, pp. 3-10, 1970.
• 52: {52} J. Sklansky, "Measuring concavity on a rectangular mosaic," <i>IEEE Trans. Comput.</i>, vol. C-21, no. 12, pp, 1355-1364, 1972 (also Subsection B.1).
• 53: {53} J. Sklansky, R. L. Chazin, and B. J. Hansen, "Minimum-perimeter polygons of digitized silhouettes," <i>IEEE Trans. Comput.</i>, vol. C-21, no. 3, pp. 260-268, Mar. 1972.
• 54: {54} J. Sklansky and D. F. Kibler, "A theory of nonuniformly digitized binary pictures," <i>IEEE Trans. Syst., Man, Cybern.</i>, vol. SMC-6, no. 9, pp. 637-647, Sept. 1976.
• 55: {55} T. Thong, "A symmetric algorithm for line segment generation," <i>Comput. Graphics</i>, vol. 6, no. 1, pp. 15-17, 1982.
• 56: {56} A. M. Vossespoel and A. W. M. Smeulders, "Statistical properties of digitized line segments," in <i>Comput. Graphics 81</i>, London, Oct. 1981, pp. 471-483.
• 57: {57} A. M. Vossespoel and A. W. M. Smeulders, "Vector code probability and metrication error in the representation of straight lines of finite length," <i>Comput. Graphics Image Processing</i>, vol. 20, no. 4, pp. 347-364, Dec. 1982.
• 58: {58} L. D. Wu, "On the Freeman's conjecture about the chain code of a line," in <i>Proc. 5th ICPR</i>, Dec, 1980, pp. 32-34.
• 59: {59} L. D. Wu, "On the chain code of a line," <i>IEEE Trans. Pattern Anal. Machine Intell.</i>, vol. PAMI-4, no. 3, pp. 347-353, May 1982.
• 60: {60} "Corrigendum on convex hull algorithms," <i>Inform. Processing Lett.</i>, vol. 10, no. 3, p. 168, Apr. 1980.
• 61: {61} S. G. Akl, "Two remarks on a convex hull algorithm," <i>Inform. Processing Lett.</i>, vol. 8, no. 2, pp. 108-109, Feb. 1979.
• 62: {62} S. G. Akl, "A constant-time parallel algorithm for computing convex hulls," <i>BIT</i>, vol. 22, no. 2, pp. 130-134, 1982.
• 63: S G. Akl, Optimal parallel algorithms for computing convex hulls and for sortng, Computing, v.33 n.1, p.1-11, 1984 [doi>10.1007/BF02243071]
• 64: {64} S. G. Akl, "Optimal parallel algorithms for selection, sorting and computing convex hulls," in <i>Computational Geometry</i>, G. T. Toussaint, Ed. Amsterdam, The Netherlands: North-Holland, 1985, pp. 1-22.
• 65: {65} S. G. Akl and G. T. Toussaint, "A fast convex hull algorithm," <i>Inform. Processing Lett.</i>, vol. 7, no. 5, pp. 219-222, Aug. 1978.
• 66: {66} S. G. Akl and G. T. Toussaint, "Efficient convex hull algorithms for pattern recognition applications," in <i>Proc. 4th IJCPR</i>, Nov. 1978, pp. 483-487.
• 67: D C. S. Allison , M T. Noga, Some performance tests of convex hull algorithms, BIT, v.24 n.1, p.2-13, 1984 [doi>10.1007/BF01934510]
• 68: {68} K. R. Anderson, "A reevaluation of an efficient algorithm for determining the convex hull of a finite planar set," <i>Inform. Processing Lett.</i>, vol. 7, no. 1, pp. 53-55, Jan. 1978.
• 69: {69} A. M. Andrew, "Another efficient algorithm for convex hulls in two dimensions," <i>Inform. Processing Lett.</i>, vol. 9, no. 5, pp. 216- 219, Dec. 1979.
• 70: {70} A. Appel and P. M. Will, "Determining the three-dimensional convex hull of a polyhedron," <i>IBM J. Res. Develop.</i>, vol. 20, no. 6, pp. 590-601, Nov. 1976.
• 71: {71} C. Arcelli and L. Cordelia, "Concavity point detection by iterative arrays," <i>Comput. Graphics Image Processing</i>, vol. 3, no. 1, pp. 34-47, Mar. 1974.
• 72: {72} C. Arcelli and S. Levialdi, "Concavity extraction by parallel processing," <i>IEEE Trans. Syst., Man, Cybern.</i>, vol. SMC-1, no. 4, pp. 394-396, Oct. 1971.
• 73: Mikhail J Atallah, Computing the convex hull of line intersections, Journal of Algorithms, v.7 n.2, p.285-288, June 1986 [doi>10.1016/0196-6774(86)90010-6]
• 74: {74} B. G. Batchelor, "Two methods for finding convex hulls of planar figures," <i>Cybern. Syst.</i>, vol. 11, no. 1-2, pp. 105-113, 1980.
• 75: Jon Louis Bentley , Franco P. Preparata , Mark G. Faust, Approximation algorithms for convex hulls, Communications of the ACM, v.25 n.1, p.64-68, Jan. 1982 [doi>10.1145/358315.358392]
• 76: {76} B. K. Bhattacharya and H. ElGindy, "A new linear convex hull algorithm for simple polygons," <i>IEEE Trans. Inform. Theory</i>, vol. IT-30, no. 1, pp. 85-88, Jan. 1984.
• 77: {77} B. K. Bhattacharya and G. T. Toussaint, "Time-and storage-efficient implementation of an optimal convex hull algorithm," <i>Image Vision Comput.</i>, vol. 1, no. 3, pp. 140-144, Aug. 1983.
• 78: {78} A. Bykat, "Convex hull of a finite set of points in two dimensions," <i>Inform. Processing Lett.</i>, vol. 7, no. 6, pp. 296-298, Oct. 1978.
• 79: Donald R. Chand , Sham S. Kapur, An Algorithm for Convex Polytopes, Journal of the ACM (JACM), v.17 n.1, p.78-86, Jan. 1970 [doi>10.1145/321556.321564]
• 80: G. H. Chen , M.-S. Chern , R. C. T. Lee, A new systolic architecture for convex hull and half-plane intersection problems, BIT, v.27 n.2, p.141-147, 1987 [doi>10.1007/BF01934178]
• 81: {81} A. L. Chow, "A parallel algorithm for determining convex hulls of sets of points in two dimensions," in <i>Proc. 19th Annu. Allerton Conf. Communication, Control, Computing</i>, Monticello, IL, 1981, pp. 214-223.
• 82: {82} V. U. Degtyar and M. Ya. Finkel'shteyn, "Classification algorithms based on construction of convex hulls of sets," <i>Eng. Cybern. </i>, vol. 12, pp. 150-154, 1974 (also Section D).
• 83: {83} F. Dévai and T. Szendrényi, "Comments on convex hull of a finite set of points in two dimensions," <i>Inform. Processing Lett.</i>, vol. 9, no. 3, pp. 141-142, Oct. 1979.
• 84: William F. Eddy, A New Convex Hull Algorithm for Planar Sets, ACM Transactions on Mathematical Software (TOMS), v.3 n.4, p.398-403, Dec. 1977 [doi>10.1145/355759.355766]
• 85: {85} E. W. Dijkstra, <i>A Discipline of Programming</i>. Englewood Cliffs, NJ: Prentice-Hall, 1976, ch. 24: "The problem of the convex hull in three dimensions," pp. 168-191; Erratum, Manuscript EWD598-0.
• 86: {86} D. J. Evans and S. Mai, "Two parallel algorithms for the convex hull problem in a two dimensional space," <i>Parallel Comput.</i>, vol. 2, no. 4, pp. 313-326, Dec. 1985.
• 87: {87} A. Fournier, "Comments on convex hull of a finite set of points in two dimensions," <i>Inform. Processing Lett.</i>, vol. 8, no. 4, p. 173, Apr. 1979.
• 88: S K Ghosh, A note on convex hull algorithms, Pattern Recognition, v.19 n.1, p.75, Jan./Feb. 1986 [doi>10.1016/0031-3203(86)90035-X]
• 89: {89} S. K. Ghosh and R. K. Shyamasundar, "A linear time algorithm for obtaining the convex hull of a simple polygon," <i>Pattern Recognition </i>, vol. 16, no. 6, pp. 587-592, 1983.
• 90: S K. Ghosh , R K. Shyamasundar, A linear time algorithm for computing the convex hull of an ordered crossing polygon , Pattern Recognition, v.17 n.3, p.351-358, 1984 [doi>10.1016/0031-3203(84)90086-4]
• 91: M. T. Goodrich, Finding the convex hull of a sorted point set in parallel, Information Processing Letters, v.26 n.4, p.173-179, Dec. 4, 1987 [doi>10.1016/0020-0190(87)90002-0]
• 92: {92} R. L. Graham, "An efficient algorithm for determining the convex hull of a finite planar set," <i>Inform. Processing Lett.</i> vol. 1, no. 4, pp. 132-133, June 1972.
• 93: {93} R. L. Graham and F. F. Yao, "Finding the convex hull of a simple polygon," <i>J. Algorithms</i>, vol. 4, no. 4, pp. 324-331, Dec. 1983.
• 94: {94} P. J. Green and B. W. Silverman, "Constructing the convex hull of a set of points in the plane," <i>Comput. J.</i>, vol. 22, no. 3, pp. 262-266, Aug. 1979.
• 95: David Gries, A note on Graham`s convex hull algorithm, Information Processing Letters, v.25 n.5, p.323-328, July 10, 1987 [doi>10.1016/0020-0190(87)90207-9]
• 96: C. C. Handley, Efficient planar convex hull algorithm, Image and Vision Computing, v.3 n.1, p.29-35, Feb. 1985 [doi>10.1016/0262-8856(85)90040-X]
• 97: {97} A. Hübler, R. Klette, and K. Voß, "Determination of the convex hull of a finite set of planar points within linear time," <i>Elektron. Informationsverarb. Kybernet</i>, vol. 17, no. 2-3, pp. 121-139, 1981.
• 98: {98} R. A. Jarvis, "On the identification of the convex hull of a finite set of points in the plane," <i>Inform. Processing Lett.</i>, vol. 2, no. 1, pp. 18-21, Mar. 1973.
• 99: {99} G. H. Johansen and C. Gram, "A simple algorithm for building the 3-D convex hull," <i>BIT</i>, vol. 3, no. 2, pp. 146-160, 1983.
• 100: {100} A. Józwik, "A method for solving the <i>n</i>-dimensional convex hull problem," <i>Pattern Recognition Lett.</i>, vol. 2, no. 1, pp. 23-25, Oct. 1983.
• 101: M Kallay, Convex hull made easy, Information Processing Letters, v.22 n.3, p.161-161, March 1986 [doi>10.1016/0020-0190(86)90064-5]
• 102: {102} B. S. Kang, "Computer construction of the convex hull of a finite set of points in space (Chinese. English summary)," <i>J. Northwest Univ.</i>, vol. 15, no. 3, pp. 17-23, 1985.
• 103: David G Kirkpatrick , Raimund Seidel, The ultimate planar convex hull algorithm, SIAM Journal on Computing, v.15 n.1, p.287-299, Feb. 1986 [doi>10.1137/0215021]
• 104: {104} R. Klette, "On the approximation of convex hulls of finite grid point sets," <i>Pattern Recognition Lett.</i>, vol. 2, no. 1, pp. 19-22, Oct. 1983.
• 105: {105} J. Koplowitz, and D. Jouppi, "A more efficient covex hull algorithm," <i>Inform. Processing Lett.</i>, vol. 7, no. 1, pp. 56-57, Jan. 1978.
• 106: {106} D. T. Lee, "On finding the convex hull of a simple polygon," <i>Int. J. Comput. Inform. Sci</i>., vol. 12, no. 2, pp. 87-98, Apr. 1983.
• 107: Dhruva Nath , S. N. Maheshwari , P. C. P. Bhatt, Parallel algorithms for the convex hull problem in two dimensions, Proceedings of the Conference on Analysing Problem Classes and Programming for Parallel Computing, p.358-372, June 10-12, 1981
• 108: {108} A. Maus, "Delaunay triangulation and the convex hull of <i>n</i> points in expected linear time," <i>BIT</i>, vol. 24, no. 2, pp. 151-163, 1984.
• 109: {109} D. McCallum and D. Avis, "A linear algorithm for finding the convex hull of a simple polygon," <i>Inform. Processing Lett.</i>, vol. 9, no. 5, pp. 201-206, Dec. 1979.
• 110: {110} M. M. McQueen and G. T. Toussaint, "On the ultimate convex hull algorithm in practice," <i>Pattern Recognition Lett.</i>, vol. 3, no. 1, pp. 29-34, Jan. 1985.
• 111: Avraham A. Melkman, On-line construction of the convex hull of a simple polyline, Information Processing Letters, v.25 n.1, p.11-12, 20 April 1987 [doi>10.1016/0020-0190(87)90086-X]
• 112: {112} Y. J. Mu, "Computer construction of the convex hull of finite point sets (Chinese. English summary)" <i>J. Northwest Univ.</i>, vol. 12, no. 2, pp. 28-34, 1982.
• 113: {113} M. Orlowski, "On the conditions for success of Sklansky's convex hull algorithm," <i>Pattern Recognition</i>, vol. 16, no. 6, pp. 579-586, 1983.
• 114: {114} M. Orlowski, "A convex hull algorithm for planar simple polygons," <i>Pattern Recognition</i>, vol. 18, no. 5, pp. 361-366, 1985.
• 115: {115} M. H. Overmars and J. van Leeuwen, "Further comments on Bykats convex hull alogrithm," <i>Inform. Processing Lett.</i>, vol. 10, no. 4-5, pp. 209-212, July 1980.
• 116: F. P. Preparata, An optimal real-time algorithm for planar convex hulls, Communications of the ACM, v.22 n.7, p.402-405, July 1979 [doi>10.1145/359131.359132]
• 117: F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
• 118: {118} D. Rutovitz, "An algorithm for in-line generation of a convex cover," <i>Comput. Graphics Image Processing</i>, vol. 4, no. 1, pp. 74-78, Mar. 1975.
• 119: Alejandro A. Schäffer , Christopher J. Van Wyk, Convex hulls of piecewise-smooth Jordan curves, Journal of Algorithms, v.8 n.1, p.66-94, March 1987 [doi>10.1016/0196-6774(87)90028-9]
• 120: Raimund Seidel, A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions, University of British Columbia, Vancouver, BC, Canada, 1981
• 121: R Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.404-413, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12172]
• 122: {122} J. Sklansky, "On filling cellular concavities," <i>Comput. Graphics & Image Processing</i>, vol. 4, no. 3, pp. 236-247, Sept. 1975.
• 123: {123} J. Sklansky, "Finding the convex hull of a simple polygon," <i>Pattern Recognition Lett.</i>, vol. 1, no. 2, pp. 79-83, Dec. 1982.
• 124: {124} J. Sklansky, L. P. Cordella, and S. Levialdi, "Parallel detection of concavities in cellular blobs," <i>IEEE Trans. Comput.</i>, vol. C- 25, no. 2, pp. 187-196, Feb. 1976.
• 125: {125} S. Y. Shin and T. C. Woo, "Finding the convex hull of a simple polygon in linear time," <i>Pattern Recognition</i>, vol. 19, no. 6, pp. 453-458, 1986.
• 126: {126} E. Soisalon-Soininen, "On computing approximate convex hulls," <i>Inform. Processing Lett.</i>, vol. 16, no. 3, pp. 121-126, Apr. 1983.
• 127: Ivan Stojmenovic9aw , Eljas Soisalon-Soininen, A note on approximate convex hulls, Information Processing Letters, v.22 n.2, p.55-56, 1986 [doi>10.1016/0020-0190(86)90140-7]
• 128: {128} I. Stojmenovic´ and D. J. Evans, "Comments on two parallel algorithms tor the convex hull problem," <i>Parallel Comput.</i>, vol. 5, no. 3, pp. 373-375, Nov. 1987.
• 129: {129} G. Swart, "Finding the convex hull facet by facet," <i>J. Algorithms</i>, vol. 6, no. 1, pp. 17-48, Mar. 1985.
• 130: {130} G. T. Toussaint, "A historical note on convex hull finding algorithms," <i>Pattern Recognition Lett.</i>, vol. 3, no. 1, pp. 21-28, Jan. 1985.
• 131: {131} G. T. Toussaint, "An optimal algorithm for computing the relative convex hull of a set of points in a polygon," in <i>Signal Processing III: Theories and Applications. 3rd European Signal Processing Conf.</i>, Sept. 1986, pp. 853-856.
• 132: {132} G. T. Toussaint and D. Avis, "On a convex hull algorithm for polygons and its application to triangulation problems," <i>Pattern Recognition</i>, vol. 15, no. 1, pp. 23-29, 1982.
• 133: {133} G. T. Toussaint and H. ElGindy, "A counterexample to an algorithm for computing monotone hulls of simple polygons," <i>Pattern Recognition Lett.</i>, vol. 1, no. 4, pp. 219-222, May 1983.
• 134: {134} M. Yau and S. N. Srihari, "Digital convex hulls from hierarchical data structures," in <i>Proc. Canadian Man-Comput. Commun. Soc. Conf.</i>, 1981, pp. 163-171 (also Section A).
• 135: {135} Z. Y. Zhou, "A real time algorithm for two-dimensional convex hull problem (Chinese. English summary)," <i>Chinese J. Comput.</i>, vol. 8, no. 2, pp. 136-143, 1985.
• 136: {136} D. Avis, "Comments on a lower bound for convex hull determination," <i>Inform. Processing Lett.</i>, vol. 11, no. 3, p. 126, Nov. 1980.
• 137: {137} D. Avis, "On the complexity of finding the convex hull of a set of points," <i>Discr. Appl. Math.</i>, vol. 4, no. 2, pp. 81-86, Apr. 1982.
• 138: J. L. Bentley , H. T. Kung , M. Schkolnick , C. D. Thompson, On the Average Number of Maxima in a Set of Vectors and Applications, Journal of the ACM (JACM), v.25 n.4, p.536-543, Oct. 1978 [doi>10.1145/322092.322095]
• 139: {139} J. L. Bentley and M. I. Shamos, "Divide and conquer for expected linear time," <i>Inform. Processing Lett.</i>, vol. 7, no. 2, pp. 87-91, Feb. 1978.
• 140: {140} H. Carnal, "Die konvexe Hülle von <i>n</i> rotationssymmetrisch verteilten Punkten," <i>Z. Wahrscheinlichkeits</i>, vol. 15, pp. 168-176, 1970.
• 141: {141} L. Devroye, "A note on finding convex hulls via maximal vectors," <i>Inform. Processing Lett.</i>, vol. 11, no. 1, pp. 53-56, Aug. 1980.
• 142: {142} L. Devroye, "How to reduce the average complexity of convex hull algorithms," <i>Comput. Math. Applicat.</i>, vol. 7, pp. 299-308, 1981.
• 143: {143} L. Devroye, "On the computer generation of random convex hulls," <i>Comput. Math. Applicat.</i>, vol. 8, pp.1-13, 1982.
• 144: {144} L. Devroye and G. T. Toussaint, "A note on linear expected time algorithms for finding convex hulls," <i>Computing</i>, vol. 16, no. 4, pp 361-366, 1981.
• 145: {145} B. Efron, "The convex hull of a random set of points," <i>Biometrika </i>, vol. 52, pp. 331-334, 1985.
• 146: {146} P. van Erode Boas, "On the Ω(<i>n</i> log <i>n</i>) lower bound for convex hull and maximal vector determination," <i>Inform. Processing/ Lett.</i>, vol. 10, no. 3, pp. 132-136, Apr. 1980.
• 147: {147} J. W. Jaromczyk, "Linear decision trees are too weak for convex hull problems," <i>Inform, Processing Lett.</i>, vol. 12, no. 3, pp. 138- 141, June 1981.
• 148: {148} M. Kallay, "The complexity of incremental convex hull algorithms in <i>R^d," Inform. Processing Lett.</i>, vol. 19, no. 4, p. 197, Nov. 1984.
• 149: Andrew Klapper, A lower bound on the complexity of the convex hull problem for simple polyhedra, Information Processing Letters, v.25 n.3, p.159-161, May 29, 1987 [doi>10.1016/0020-0190(87)90126-8]
• 150: {150} H. Raynaud, "Sur l'enveloppe convexe des nuages de points aléatoires dans <i>R</i><inf>n</inf> I," <i>J. Appl. Probability</i>, vol. 7, pp. 35-48, 1970.
• 151: {151} A. Rényi and R. Sulanke, Über die konvexe Hülle von <i>n</i> zufällig gewählten Punkten, I," <i>Z. Wahrscheinlichkeits</i>, vol. 2, pp. 75- 84, 1963, II, vol. 3, pp. 138-147, 1964.
• 152: {152} A. Rényi and R. Sulanke "Zufällige konvexe Polygone in einem Ringgebeit," <i>Z. Wahrscheinlichkeits</i>, vol. 9, pp. 146-157, 1968.
• 153: Andrew Chi-Chih Yao, A Lower Bound to Finding Convex Hulls, Journal of the ACM (JACM), v.28 n.4, p.780-787, Oct. 1981 [doi>10.1145/322276.322289]
• 154: {154} H. Ziezold, "Über die Eckenzahl zufälliger konvexer Polygone," <i>Izv. Akad. Nauk. Armanj. SSR. Ser. Mat.</i>, vol. 5, pp. 296-312, 1970.
• 155: {155} A. Aggarwal, B. Chazelle, L. Guibas, C. Ó'Dúnlaig, and C. Yap, "Parallel computational geometry," <i>Algorithmica</i>, vol. 3, no. 3, pp. 293-327, 1988.
• 156: {156} A. Aggarwal, M. M. Klawe, S. Moran, P. Shor, and R. Wilberg, "Geometric applications of a matrix-searching algorithm," <i>Algorithmica </i>, vol. 2, no. 2, pp. 195-208, 1987.
• 157: {157} M. J. Atallah and M. T. Goodrich, "Parallel algorithms for some functions of two convex polygons," in <i>Proc. 24th Annu. Allerton Conf. Communication, Control, Computing</i>, Monticello, IL, 1986, pp. 758-767.
• 158: {158} G. D. Chakerian and L. H. Lange, "Geometric extremum problems," <i>Math, Mag.</i>, vol. 44, no. 1, pp. 57-69, Jan 1971.
• 159: {159} B. M. Chazelle, "A theorem on polygon cutting with applications," in <i>Proc. IEEE 23rd Ann. Symp. Foundations of Computer Science</i>, 1982, pp. 339-349.
• 160: Bernard Chazelle , David P. Dobkin, Detection is easier than computation (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.146-153, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804662]
• 161: {161} F. Chin, J. Sampson, and C. A. Wang, "A unifying approach for a class of problems in the computational geometry of polygons," <i>Visual Comput.</i>, vol. 1, no. 2, pp. 124-132, 1985.
• 162: {162} L. Devroye, "Recent results of the average time behavior of some algorithms in computational geometry," in <i>Comput. Science and Statisitcs: Proc. 13th Symp. Interface</i>, W. F. Eddy, Ed. Berlin: Springer-Verlag, 1981, pp. 76-82.
• 163: {163} L. Devroye, "Expected time analysis of algorithms in computational geometry," in <i>Computational Geometry</i>, G. T. Toussaint, Ed. Amsterdam, The Netherlands: North-Holland, 1985, pp. 135- 151 (also Subsection B.2).
• 164: {164} D. P. Dobkin and L. Snyder, "On a general method for maximizing and minimizing among certain geometric problems," in <i>Proc. IEEE 20th Annu. Symp. Foundations of Computer Science</i>, 1979, pp. 9-17.
• 165: H Edelsbrunner , L J Guibas, Topologically sweeping an arrangement, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.389-403, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12171]
• 166: {166} H. ElGindy, D. Avis, and G. T. Toussaint, "Applications of a two-dimensional hidden-line algorithm to other geometric problems," <i>Computing</i>, vol. 31, no. 3, pp. 191-202, 1983.
• 167: {167} W. Henze, "Zur VLSI-Kompliziertheit geometrischer Berechnungsprobleme," Sektion Mathematik, Humboldt, Univ,, Berlin, 1985.
• 168: Alfred Inselberg , Mordechai Reif , Tuval Chomut, Convexity algorithms in parallel coordinates, Journal of the ACM (JACM), v.34 n.4, p.765-801, Oct. 1987 [doi>10.1145/31846.32221]
• 169: {169} D. T. Lee and F. P. Preparata, "Computational geometry-A survey," <i>IEEE Trans. Comput.</i>, vol. C-33, no. 12, pp. 1072-1101, Dec. 1984, Correction, vol. C-34, no. 6, p. 584, June 1985.
• 170: {170} G. Nagy, "Advances in computational geometry," in <i>Proc. 21st Midwest Symp. Circuits and Systems</i>, 1978, pp. 598-603.
• 171: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 172: {172} R. Seidel, "A method for proving lower bounds for certain geometrical problems," in <i>Computational Geometry,</i>, G. T. Toussaint, Ed. Amsterdam, The Netherlands: North-Holland, 1985, pp. 319- 334.
• 173: Michael Ian Shamos, Geometric complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.224-233, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803772]
• 174: {174} M. I. Shamos, and D. Hoey, "Closest-point problems," in <i> Proc. IEEE 16th Annu. Symp. Foundations of Computer Science</i>, 1975, pp. 151-162.
• 175: {175} G. T. Toussaint, "Pattern recognition and geometric complexity," in Proc. 5th ICPR, Dec. 1980, pp. 1324-1347.
• 176: {176} G. T. Toussaint, "Computational geometric problems in pattern recognition," in <i>Pattern Recognition Theory and Applications</i>, J. Kittler, K. S. Fu, and L. F. Pau, Eds. Dordrecht, The Netherlands: Reidel, 1982, pp. 73-91.
• 177: {177} G. T. Toussaint, "Complexity, convexity, and unimodality," <i>Int. J. Comput. Inform. Sci.</i>, vol. 13, no. 3, pp. 197-217, June 1984.
• 178: {178} G. T. Toussaint, Ed., <i>Computational Geometry</i>. Amsterdam, The Netherlands: North-Holland, 1985.
• 179: {179} G. T. Toussaint, "New results in computational geometry relevant to pattern recognition in practice," in <i>Pattern Recognition in Practice II</i>, E. S. Gelsema and L. N. Kanal, Eds. Amsterdam, The Netherlands: North-Holland, 1986, pp. 135-146.
• 180: {180} W. Altherr, "An algorithm for enumerating all vertices of a convex polyhedron," <i>Computing</i>, vol. 15, no. 3, pp. 181-193, 1975.
• 181: {181} M. L. Balinski, "An algorithm for finding all vertices of convex polyhedral sets," <i>J. SIAM</i>, vol. 9, no. 1, pp. 72-88, Mar. 1961.
• 182: {182} I. Bárány and Z. Füredi, "Computing the volume is difficult," <i>Discr. Comput. Geom.</i>, vol. 2, no. 4, pp. 319-326, 1987.
• 183: {183} B. K. Bhattacharya and G. T. Toussaint, "A counterexample to a diameter algorithm for convex polygons," <i>IEEE Trans. Pattern Anal. Machine Intell.</i>, vol. PAMI-4, no. 3, pp. 306-309, May 1982.
• 184: {184} C. A. Burdet, "Generating all the faces of a polyhedron," <i>SIAM J. Appl. Math.</i>, vol. 26, no. 3, pp. 479-489, May 1974.
• 185: Jacques Cohen , Timothy Hickey, Two Algorithms for Determining Volumes of Convex Polyhedra, Journal of the ACM (JACM), v.26 n.3, p.401-414, july 1979 [doi>10.1145/322139.322141]
• 186: {186} M. E. Dyer and L. G. Proll, "An algorithm for determining all extreme points of a convex polytope," <i>Math. Program.</i>, vol. 12. pp. 81-96, 1977.
• 187: {187} G. Elekes, "A geometric inequality and the complexity of computing volume," <i>Discr. Comput. Geom.</i>, vol. 1, no. 4, pp. 289- 292, 1986.
• 188: {188} J. B. Lasserre, "An analytical expression and an algorithm for the volume of a convex polyhedron in <i>R</i>ⁿ," <i>J. Optimization Theory Applicat.</i>, vol. 39, no. 3, pp. 363-377, Mar. 1983.
• 189: {189} M. Manas, "Methods for finding all vertices of a convex polyhedron," <i>Ekonom. I Mat. Obzor</i>, vol. 5, pp. 325-342, 1969.
• 190: {190} M. Manas and J. Nedoma, "Finding all vertices of a convex polyhedron," <i>Numerische Mathematik</i>, vol. 12, no. 3, pp. 226- 229, 1968.
• 191: {191} T. H. Mattheiss and D. Rubin, "A survey and comparison of methods for finding all vertices of convex polyhedral sets," <i>Math. Oper. Res.</i>, vol. 5, no. 2, pp. 167-185, May 1980.
• 192: {192} T. H. Mattheiss and B. K. Schmidt, "Computational results on an algorithm for finding all vertices of a polytope," <i>Math. Program.</i>, vol. 18, pp. 308-329, 1980.
• 193: {193} W. E. Snyder and D. A. Tang, "Finding the extrema of a region," <i>IEEE Trans. Pattern Anal. Machine Intell.</i>, vol. PAMI-2, no. 3, pp. 266-269, May 1980.
• 194: {194} W. E. Snyder and D. A. Tang, "Comments on "A counterexample to a diameter algorithm for convex polygons," <i>IEEE Trans. Pattern Anal. Machine Intell.</i>, vol. PAMI-4, no. 3, p. 309, May 1982.
• 195: Ted Speevak, An efficient algorithm for obtaining the volume of a special kind of pyramid and application to convex polyhedra, Mathematics of Computation, v.46 n.174, p.531-536, April 1986 [doi>10.2307/2007991]
• 196: T. Bailey , J. Cowles, A convex hull inclusion test, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.9 n.2, p.312-316, March 1987 [doi>10.1109/TPAMI.1987.4767904]
• 197: {197} J. L. Bentley and W. Carruthers, "Algorithms for testing the inclusion of points in polygons," in <i>Proc. 18th Annu. Allerton Conf. Communication, Control. Computing</i>, Monticello, IL, 1980, pp. 11-19.
• 198: Richard Cole, Searching and sorting similar lists, Journal of Algorithms, v.7 n.2, p.202-220, June 1986 [doi>10.1016/0196-6774(86)90004-0]
• 199: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• 200: {200} D. G. Kirkpatrick, "Optimal search in planar subdivisions," <i>SIAM J. Comput</i>, vol. 12, no. 1, pp. 28-35, Feb. 1983.
• 201: {201} D. T. Lee and F. P. Preparata, "Location of a point in a planar subdivision and its applications," <i>SIAM J. Comput.</i>, vol. 6, no. 3, pp. 594-606, Sept. 1977.
• 202: {202} R. J. Lipton and R. E. Tarjan, "Applications of a planar separator theorem," in <i>Proc. IEEE 18th Annu. Symp. Foundations of Computer Science</i>, 1977, pp. 162-170.
• 203: {203} S. Nordbeck and B. Rysted, "Computer cartography point-inpolygon programs," <i>BIT</i>, vol. 7, no. 1, pp. 39-64, 1967 (also Section D).
• 204: {204} F. P. Preparata, "A new approach to planar point location," <i>SIAM J. Comput.</i>, vol. 10, no. 3, pp. 473-482, Aug. 1981.
• 205: {205} K. B. Salomon, "An efficient point-in-polygon algorithm," <i>Comput. Geosci.</i>, vol. 4, pp. 173-178, 1978.
• 206: Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
• 207: {207} M. Boyer and L. Paquette, "An algorithm to decide if the intersection of convex polyhedral cones has non empty interior," <i>BIT</i>, vol. 16, no. 4, pp. 459-461, 1976 (also Section D).
• 208: B. Chazelle , D. P. Dobkin, Intersection of convex objects in two and three dimensions, Journal of the ACM (JACM), v.34 n.1, p.1-27, Jan. 1987 [doi>10.1145/7531.24036]
• 209: {209} F. Chin and C. A. Wang, "Optimal algorithm for the intersection and minimum distance problems between planar polygons," <i>IEEE Trans. Comput.</i>, vol. C-32, no. 12, pp. 1203-1207, Dec. 1983 (also Subsection C.5).
• 210: Paul G. Comba, A Procedure for Detecting Intersections of Three-Dimensional Objects, Journal of the ACM (JACM), v.15 n.3, p.354-366, July 1968 [doi>10.1145/321466.321468]
• 211: {211} D. P. Dobkin and D. G. Kirkpatrick, "Fast detection of polyhedral intersections," <i>Theoret. Comput. Sci.</i>, vol. 27, no. 3, pp. 241- 253, Dec. 1983.
• 212: {212} S. Hertel, M. Mäntilä, K. Mehlhorn, and J. Nievergelt, "Space sweep solves intersection of convex polyhedra," <i>Acta Inform.</i>, vol. 21, no. 5, pp. 501-519, 1984.
• 213: Sukhamay Kundu, A new O(n ˙logn) algorithm for computing the intersection of convex polygons, Pattern Recognition, v.20 n.4, p.419-424, 1987 [doi>10.1016/0031-3203(87)90067-7]
• 214: {214} K. Maruyama, "A procedure to determine intersections between polyhedral objects," <i>Int. J. Comput. Inform. Sci.</i>, vol. 1, no. 3, pp. 255-266, Sept. 1972.
• 215: Kurt Mehlhorn , Klaus Simon, Intersecting two polyhedra one of which is convex, Fundamentals of Computation Theory, p.534-542, September 09-13, 1985
• 216: {216} D. E. Muller and F. P. Preparata, "Finding the intersection of two convex polyhedra," <i>Theoret. Comput. Sci.</i>, vol. 7, no. 2, pp. 217- 236, Oct. 1978.
• 217: J. Nievergelt , F. P. Preparata, Plane-sweep algorithms for intersecting geometric figures, Communications of the ACM, v.25 n.10, p.739-747, Oct 1982 [doi>10.1145/358656.358681]
• 218: {218} J. O'Rourke, C. B. Chien, T. Olson and D. Naddor, "A new linear algorithm for intersecting convex polygons," <i>Comput. Graphics Image Processing</i>, vol. 19, no. 4, pp. 384-391, Aug. 1982.
• 219: {219} M. I. Shamos and D. Hoey, "Geometric intersection problems," <i>Proc. IEEE 7th Annu. Symp. Foundations of Computer Science</i>, 1976, pp. 208-215.
• 220: {220} S. Storøy, "An algorithm for finding a vector in the intersection of open convex polyhedral cones," <i>BIT</i>, vol. 13, no. 1, pp. 114- 119, 1973 (also Section D).
• 221: {221} G. T. Toussaint, "A simple linear algorithm for intersecting convex polygons," <i>Visual Comput.</i>, vol. 1, no. 2, pp. 118-123, 1985.
• 222: {222} M. J. Atallah, "A linear time algorithm for the Hausdorff distance between convex polygons," <i>Inform. Processing Lett.</i>, vol. 17, no. 4, pp. 207-209, Nov. 1983.
• 223: {223} M. J. Atallah and M. T. Goodgrich, "Parallel algorithms for some functions of two convex polygons," <i>Algorithmica</i>, vol. 3, no. 4, pp. 535-548, 1988 (also Subsection C. 10).
• 224: {224} D. Avis, G. T. Toussaint, and B. K. Bhattacharya, "On the multimodality of distances in convex polygons," <i>Comput. Math. Applicat. </i>, vol. 8, no. 2, pp. 153-156, 1982.
• 225: Avikam Balstan , Micha Sharir, On the shortest paths between two convex polyhedra, Journal of the ACM (JACM), v.35 n.2, p.267-287, April 1988 [doi>10.1145/42282.214094]
• 226: {226} B. K. Bhattacharya and G. T. Toussaint, "Efficient algorithms for computing the maximum distance between two finite planar sets," <i>J. Algorithms</i>, vol. 4, no. 2, pp. 121-136, June 1983.
• 227: {227} B. K. Bhattacharya and G. T. Toussaint, "On geometric algorithms that use the furthest-point Voronoi diagram," in <i>Computational Geometry</i>, G. T. Toussaint, Ed. Amsterdam, The Netherlands: North-Holland, 1985, pp. 43- 61.
• 228: {228} F. Chin and C. A. Wang, "Minimum vertex distance between separable convex polygons," <i>Inform. Processing Lett.</i>, vol. 18, no. 1, pp. 41-45, Jan. 1984.
• 229: {229} A. K. Dewdney and J. K. Vranch, "A convex partition of <i>R</i>³ with applications to Crum's problem and Knuth's post-office problem," <i>Utilitas Math.</i>, vol. 12, pp. 193-199, 1977.
• 230: H. Edelsbrunner, Computing the extreme distances between two convex polygons, Journal of Algorithms, v.6 n.2, p.213-224, June 1985 [doi>10.1016/0196-6774(85)90039-2]
• 231: {231} A. Fournier and Z. Kedem, "Comments on the all nearest-neighbor problem for convex polygons," <i>Inform. Processing Lett.</i>, vol. 9, no. 3, pp. 105-107, Oct. 1979.
• 232: {232} D. T. Lee and F. P. Preparata, "The all nearest-neighbor problem for convex polygons," <i>Inform. Processing Lett.</i>, vol. 7, no. 4, pp. 189-192, June 1978.
• 233: {233} M. McKenna and G. T. Toussaint, "Finding the minimum vertex distance between two disjoint convex polygons in linear time,'" <i>Comput. Math. with Applicat.</i>, vol. 11, no. 12, pp. 1227-1242, 1985.
• 234: {234} J. T. Schwartz, "Finding the minimum distance between two convex polygons," <i>Inform. Processing Lett.</i>, vol. 13, no. 4-5, pp. 168-170, Dec. 1981.
• 235: G T. Toussaint, An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons, Computing, v.32 n.4, p.357-364, 1984 [doi>10.1007/BF02243778]
• 236: {236} G. T. Toussaint and B. K. Bhattacharya, "Optimal algorithms for computing the minimum distance between two finite planar sets," <i>Pattern Recognition Lett.</i>, vol. 2, no. 2, pp. 79-82, Dec. 1983.
• 237: {237} G. T. Toussaint and J. A. McAlear, "A simple <i>O</i>(<i>n</i> log <i>n</i>) algorithm for finding the maximum distances between two finite planar sets," <i>Pattern Recognition Lett.</i>, vol. 1, no. 1, pp. 21-24, Oct. 1982.
• 238: {238} C. C. Yang and D. T. Lee, "A note on the all nearest-neighbor problem for convex polygons," <i>Inform. Processing Lett.</i>, vol. 8, no. 4, pp. 193-194, Apr. 1979.
• 239: Bernard M. Chazelle, Convex decompositions of polyhedra, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.70-79, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802459]
• 240: {240} B. M. Chazelle, "A decision procedure for optimal polyhedron partitioning," <i>Inform. Processing Lett.</i>, vol. 16, no. 2, pp. 75-78, Feb. 1983.
• 241: Bernard Chazelle, Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm, SIAM Journal on Computing, v.13 n.3, p.488-507, August 1984 [doi>10.1137/0213031]
• 242: Bernard Chazelle , David Dobkin, Decomposing a polygon into its convex parts, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.38-48, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804396]
• 243: {243} B. M. Chazelle and D. P. Dobkin, "Optimal convex decompositions," in <i>Computational Geometry </i>, G. T. Toussaint, Ed. Amsterdam, The Netherlands: North-Holland, 1985, pp. 63-133.
• 244: {244} D. P. Dobkin, D. L. Souvaine, and C. J. Van Wyk, "Decomposition and intersection of simple splinegons," <i>Algorithmica</i>, vol. 3, no. 4, pp. 473-485, 1988 (also Subsection C.4).
• 245: {245} D. H. Greene, "The decomposition of polygons into convex parts," in <i>Advances in Computing Research</i>, vol. 1, F. P. Preparata, Ed. JAI Press, 1983, pp. 235-259.
• 246: {246} T. C. Hu and M. T. Shing, "An <i>O(n)</i> algorithm to find a near-optimum partition of a convex polygon," <i>J. Algorithms</i>, vol. 2, no. 2, pp. 122-138, June 1981.
• 247: {247} J. M. Keil, "Decomposing a polygon into simpler components," <i>SIAM J. Comput.</i>, vol. 14, no. 4, pp. 799-817, Nov. 1985.
• 248: {248} J. M. Keil and J. R. Sack, "Minimum decompositions of polygonal objects," in <i>Computational Geometry</i>, G. T. Toussaint, Ed. Amsterdam, The Netherlands: North-Holland, 1985, pp. 197-216.
• 249: Christos Levcopoulos , Andrzej Lingas, Bounds on the Length of Convex Partitions of Polygons, Proceedings of the Fourth Conference on Foundations of Software Technology and Theoretical Computer Science, p.279-295, December 13-15, 1984
• 250: Anna Lubiw, Decomposing polygonal regions into convex quadrilaterals, Proceedings of the first annual symposium on Computational geometry, p.97-106, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323247]
• 251: {251} J. O'Rourke and K. J. Supowit, "Some NP-hard polygon decomposition problems," <i>IEEE Trans. Inform. Theory</i>, vol. IT-29, no. 2, pp. 181-190, Mar. 1983.
• 252: {252} J. R. Sack, "A <i>O</i>(<i>n</i> log <i>n</i>) algorithm for decomposing rectilinear polygons into convex quadrilaterals," in <i>Proc. 20th Annu. Allerton Conf. Communications, Control and Computing</i>, Monticello, IL, 1982, pp. 64-74.
• 253: {253} J. R. Sack and G. T. Toussaint, "A linear-time algorithm for decomposing rectilinear star-shaped polygons into convex quadrilaterals," in <i>Proc. 19th Annu. Allerton Conf. Communication, Control and Computing</i>, Monticello, IL, 1981, pp. 21-30.
• 254: {254} B. Schachter, "Decomposition of polygons in convex sets," <i>IEEE Trans. Comput.</i>, vol. C-27, no. 11, pp. 1078-1082, Nov. 1978.
• 255: S. B. Tor , A. E. Middleditch, Convex Decomposition of Simple Polygons, ACM Transactions on Graphics (TOG), v.3 n.4, p.244-265, Oct. 1984 [doi>10.1145/357346.357348]
• 256: {256} A. Aggarwal, J. S. Chang, and C. K. Yap, "Minimum area cirumscribing polygons," <i>Visual Comput.</i>, vol. 1, no. 2, pp. 112- 117, 1985.
• 257: {257} N. A. A. De Pano and A. Aggarwal, "Finding restricted <i>k</i>-envelopes for convex polygons," in <i>Proc. 22nd Annu. Allerton Conf. Communication, Control, and Computing</i>, Monticello, IL, 1984, pp. 81-90.
• 258: {258} D. Dori and M. Ben-Bassat, "Circumscribing a convex polygon by a polygon of fewer sides with minimal area addition," <i>Comput. Vision, Graphics, Image Processing</i>, vol. 24, no. 2, pp. 131-159, Nov. 1983.
• 259: {259} J. Elzinga and D. Hearn, "The minimum sphere covering a convex polyhedron," <i>Naval Res. Logistics Quart.</i>, vol. 21, pp. 715-718, 1974.
• 260: H. Freeman , R. Shapira, Determining the minimum-area encasing rectangle for an arbitrary closed curve, Communications of the ACM, v.18 n.7, p.409-413, July 1975 [doi>10.1145/360881.360919]
• 261: {261} V. Klee, "A linear-time algorithm that finds all local minima among triangles containing a given convex polygon," <i>Proc. Vth Symp. Operations Res.</i>, Köln, Aug. 1980.
• 262: {262} V. Klee and M. C. Laskowski, "Finding the smallest triangles containing a given convex polygon," <i>J. Algorithms</i>, vol. 6, no. 3, pp. 359-375, Sept. 1985.
• 263: {263} J. O'Rourke, "The complexity of computing minimum convex covers for polygons," in <i>Proc. 20th Annu. Allerton Conf. Communication, Control, and Computing</i>, Monticello, IL, 1982, pp. 75-84.
• 264: {264} J. O'Rourke, "Finding minimal enclosing boxes," <i>Int. J. Comput. Inform. Sci.</i>, vol. 14, no. 3, pp. 183-199, June 1985.
• 265: {265} J. O'Rourke, "Counterexamples to a minimal circumscription algorithm," <i>Comput. Vision Graphics, Image Processing</i>, vol. 30, no. 3, pp. 364-366, June 1985.
• 266: Joseph O'Rourke , Alok Aggarwal , Sanjeev Maddila , Michael Baldwin, An optimal algorithm for finding minimal enclosing triangles, Journal of Algorithms, v.7 n.2, p.258-269, June 1986 [doi>10.1016/0196-6774(86)90007-6]
• 267: {267} G. T. Toussaint, "Solving geometric problems with the "rotating calipers," in <i>Proc. IEEE MELECON 83</i>, Athens, Greece, May 1983.
• 268: {268} T. C. Woo and H. C. Lee, "On the time complexity for circumscribing a convex polygon," <i>Comput. Vision, Graphics, Image Processing</i>, vol. 30, no. 3, pp. 362-363, June 1985.
• 269: {269} J. S. Chang and C. K. Yap, "A polymomial solution for potatopeeling and other polygon inclusion and enclosure problems," in <i>Proc. IEEE 25th Annu. Symp. Foundations of Computer Science</i>, 1984, pp. 408-416.
• 270: {270} J. S. Chang and C. K. Yap, "A polymomial solution for the potato-peeling problem," <i>Distr. Comput. Geom.</i>, vol. 1, no. 2, pp. 155-182, 1986.
• 271: {271} V. Chvátal and G. Klincsek, "Finding largest convex subsets," in <i>Proc. 11th Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing</i>, Vol. II, Boca Raton, FL; <i>Congr. Numer.</i>, vol. 29, pp. 453-460, 1980.
• 272: {272} J. E. Goodman, "On the largest convex polygon contained in a non-convex <i>n</i>-gon, or how to peel a potato," <i>Geometriae Dedicata </i>, vol. 11, pp. 99-106, 1981.
• 273: Derick Wood , Chee K. Yap, Computing a convex skill of an orthogonal polygon, Proceedings of the first annual symposium on Computational geometry, p.311-315, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323273]
• 274: Varol Akman, Unobstructed shortest paths in polyhedral environments, Springer-Verlag New York, Inc., New York, NY, 1986
• 275: John Hershberger , Leonidas J. Guibas, An O(n2) shortest path algorithm for a non-rotating convex body, Journal of Algorithms, v.9 n.1, p.18-46, March 1988 [doi>10.1016/0196-6774(88)90003-X]
• 276: K. Kedem , M. Sharir, An efficient algorithm for planning collision-free translational motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles, Proceedings of the first annual symposium on Computational geometry, p.75-80, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323244]
• 277: {277} D. Leven and M. Sharir, "Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams," <i>Discr. Comput. Geom.</i>, vol. 2, no. 1, pp. 9- 31, 1987.
• 278: {278} D. Leven and M. Sharir, "On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space," <i>Discr. Comput. Geom.</i>, vol. 2, no. 3, pp. 255-270, 1987.
• 279: {279} J. O'Rourke, "Convex hulls, Voronoi diagrams, and terrain navigation," in <i>Proc. 9th Pecora Symp. Spatial Information Technologies for Remote Sensing Today and Tomorrow</i>, R. M. Haralick, Ed. Washington, DC: IEEE Computer Society Press, 1984, pp. 358-361.
• 280: H Rohnert, Shortest paths in the plane with convex polygonal obstacles, Information Processing Letters, v.23 n.2, p.71-76, Aug. 20, 1986 [doi>10.1016/0020-0190(86)90045-1]
• 281: Hans Rohnert, Time and space efficient algorithms for shortest paths between convex polygons, Information Processing Letters, v.27 n.4, p.175-179, April 8, 1988 [doi>10.1016/0020-0190(88)90022-1]
• 282: Micha Sharir, On shortest paths amidst convex polyhedra, SIAM Journal on Computing, v.16 n.3, p.561-572, June 1987 [doi>10.1137/0216038]
• 283: Micha Sharir , Amir Schorr, On shortest paths in polyhedral spaces, SIAM Journal on Computing, v.15 n.1, p.193-215, Feb. 1986 [doi>10.1137/0215014]
• 284: Alok Aggarwal , Heather Booth , Joseph O'Rourke , Subhash Suri , Chee K. Yap, Finding minimal convex nested polygons, Proceedings of the first annual symposium on Computational geometry, p.296-304, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323271]
• 285: Varol Akman, An algorithm for determining an opaque minimal forest of a convex polygon, Information Processing Letters, v.24 n.3, p.193-198, February 1987 [doi>10.1016/0020-0190(87)90185-2]
• 286: {286} D. Avis, H. ElGindy, and R. Seidel, "Simple on-line algorithms for convex polygons," in <i>Computational Geometry</i>, G. T. Toussaint, Ed. Amsterdam, The Netherlands: North-Holland, 1985, pp. 23-42.
• 287: David Avis , David Rappaport, Computing the largest empty convex subset of a set of points, Proceedings of the first annual symposium on Computational geometry, p.161-167, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323255]
• 288: B S Baker , S J Fortune , S R Mahaney, Polygon containment under translation, Journal of Algorithms, v.7 n.4, p.532-548, Dec. 1986 [doi>10.1016/0196-6774(86)90017-9]
• 289: {289} Y. Ben-Haim, "Convex sets and nondestructive assay," <i>SIAM J. Alg. Discr. Methods</i>, vol. 6, no. 4, pp. 688-706, Oct. 1985.
• 290: H. J. Bernstein, Determining the shape of a convex n-sided polygon by using 2n+k tactile probes, Information Processing Letters, v.22 n.5, p.255-260, April 1986 [doi>10.1016/0020-0190(86)90103-1]
• 291: James E. Boyce , David P. Dobkin , Robert L. Drysdale, III , Leo J. Guibas, Finding extremal polygons, SIAM Journal on Computing, v.14 n.1, p.134-147, Feb. 1985 [doi>10.1137/0214011]
• 292: {292} B. M. Chazelle, "The polygon containment problem," in <i>Advances in Computing Research</i>, vol. 1, F. P. Preparata, Ed. JAI Press, 1983, pp. 1-33.
• 293: {293} B. M. Chazelle, "On the convex layers of a planar set," <i>IEEE Trans. Inform. Theory</i>, vol. IT-31, no. 4, pp. 509-517, July 1985.
• 294: Richard Cole , Chee K. Yap, Shape from probing, Journal of Algorithms, v.8 n.1, p.19-38, March 1987 [doi>10.1016/0196-6774(87)90025-3]
• 295: Richard Cole , Micha Sharir , Chee K. Yap, On k-hulls and related problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.154-166, December 1984 [doi>10.1145/800057.808677]
• 296: Richard Cole , Micha Sharir , Chee K Yap, On k-hulls and related problems, SIAM Journal on Computing, v.16 n.1, p.61-77, Feb. 1987 [doi>10.1137/0216005]
• 297: Glenn Davis, Computing separating planes for pairs of disjoint polytopes, Proceedings of the first annual symposium on Computational geometry, p.8-14, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323235]
• 298: {298} D. P. Dobkin, R. L. Drysdale, and L. J. Guibas, "Finding smallest polygons," in <i>Advances in Computing Research</i>, vol. 1, F. P. Preparata, Ed. JAI Press, 1983, pp. 181-214.
• 299: D Dobkin , H Edelsbrunner , C K Yap, Probing convex polytopes, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.424-432, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12174]
• 300: {300} D. P. Dobkin and D. G. Kirkpatrick, "A linear algorithm for determining the separation of convex polyhedra," <i>J. Algorithms</i>, vol. 6, no. 3, pp. 381-392, Sept. 1985.
• 301: Dov Dori , Moshe Ben-Bassat, Efficient nesting of congruent convex figures, Communications of the ACM, v.27 n.3, p.228-235, March 1984 [doi>10.1145/357994.358022]
• 302: Herbert Edelsbrunner , Steven S. Skiena, Probing convex polygons with X-rays, SIAM Journal on Computing, v.17 n.5, p.870-882, October 1988 [doi>10.1137/0217054]
• 303: {303} L. J. Guibas and R. Seidel, "Computing convolutions by reciprocal search," <i>Discr. Comput. Geom.</i>, vol. 2, no. 2, pp. 175-193, 1987.
• 304: Dorit S. Hochbaum , Wolfgang Maass, Fast approximation algorithms for a nonconvex covering problem, Journal of Algorithms, v.8 n.5, p.305-323, Sept. 1987 [doi>10.1016/0196-6774(87)90012-5]
• 305: J M Keil, Minimally covering a horizontally convex orthogonal polygon, Proceedings of the second annual symposium on Computational geometry, p.43-51, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10520]
• 306: {306} R. Klette and E. V. Krishnamurthy, "Algorithms for testing convexity of digital polygons," <i>Comput. Graphics Image Processing</i>, vol. 16, no. 2, pp. 177-184, June 1981.
• 307: {307} D. T. Lee and I. M. Chen, "Display of visible edges of a set of convex polygons," in <i>Computational Geometry</i>, G. T. Toussaint, Ed. Amsterdam, The Netherlands: North-Holland, 1985, pp. 249-265.
• 308: {308} D. T. Lee and C. B. Silio, "An optimal illumination region algorithm for convex polygons," <i>IEEE Trans. Comput.</i>, vol. C-31, no. 12, pp. 1225-1227, Dec. 1982.
• 309: Wolfgang Maass, On the complexity of nonconvex covering, SIAM Journal on Computing, v.15 n.2, p.453-467, May 1986 [doi>10.1137/0215031]
• 310: Michael McKenna , Raimund Seidel, Finding the optimal shadows of a convex polytope, Proceedings of the first annual symposium on Computational geometry, p.24-28, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323237]
• 311: {311} A. Mesa Henriquez, "CONVY: An algorithm for the nonoverlapping covering of polygons by convex sets (Spanish, English summary)," <i>Investigación Oper.</i>, vol. 6 no. 2-3, pp. 79-94, 1985.
• 312: {312} A. Mesa Henriquez, "HODY: An algorithm for constructing the hodograph of convex polygons (Spanish. English summary)," <i>Investigación Oper.</i>, vol. 6, no. 2-3, pp. 95-110, 1985.
• 313: {313} T. M. Nicholl, D. T. Lee, Y. Z. Liao, and C. K. Wong, "On the X-Y convex hull of a set of X-Y polygons," <i>BIT</i>, vol. 23, pp. 456- 471, 1983.
• 314: {314} T. Ottmann, E. Soisalon-Soininen, and D. Wood," On the definition and computation of rectilinear convex hulls," <i>Inform. Sci.</i>, vol. 33, no. 3, pp. 157-171, 1984.
• 315: Mark H. Overmars , Jan van Leeuwen, Dynamically maintaining configurations in the plane (Detailed Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.135-145, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804661]
• 316: {316} M. H. Overmars and J. van Leeuwen, "Maintenance of configurations in the plane," <i>J. Comput. Sys. Sci.</i>, vol. 23, no. 2, pp. 166-204, Oct. 1981.
• 317: {317} J. Pach, "On an isoperimetric problem," <i>Studia Sci. Math. Hungar </i>. vol. 13, no. 1-2, pp. 43-45, 1978.
• 318: János Pach, Covering the plane with convex polygons, Discrete & Computational Geometry, v.1 n.1, p.73-81, 1986 [doi>10.1007/BF02187684]
• 319: Gregory J. E. Rawlins , Derick Wood, Optimal computation of finitely oriented convex hulls, Information and Computation, v.72 n.2, p.150-166, Feb. 1987 [doi>10.1016/0890-5401(87)90045-9]
• 320: M. Roussille , P. Dufour, Generation of convex polygons with individual angular constraints, Information Processing Letters, v.24 n.3, p.159-164, February 1987 [doi>10.1016/0020-0190(87)90179-7]
• 321: {321} J. R. Sack, "A simple hidden-line algorithm for rectilinear polygons," in <i>Proc. 21st Annu. Allerton Conf. Communication, Control and Computing</i>, Monticello, IL, 1983, pp. 437-446.
• 322: Shuo-Yen, Robert Li, Reconstruction of polygons from projections, Information Processing Letters, v.28 n.5, p.235-240, Aug. 12, 1988 [doi>10.1016/0020-0190(88)90196-2]
• 323: {323} S. P. Smith and A. K. Jain, "Testing for uniformity in multidimensional data," <i>IEEE Trans. Pattern Anal. Machine Intell.</i>, vol. PAMI-6, no. 1, pp. 73-81, Jan. 1984 (also Section D).
• 324: {324} G. T. Toussaint, "A simple proof of Pach's extremal theorem for convex polygons," <i>Pattern Recognition Lett.</i>, vol. 1, no. 2, pp. 85-86, Dec. 1982.
• 325: P. Widmayer , Y. F. Wu , C. K. Wong, On some distance problems in fixed orientations, SIAM Journal on Computing, v.16 n.4, p.728-746, Aug. 1987 [doi>10.1137/0216049]
• 326: {326} D. Wood, "An isothetic view of computational geometry," in <i>Computational Geometry</i>, G. T. Toussaint, Ed. Amsterdam, The Netherlands: North-Holland, 1985, pp. 429-459.
• 327: {327} D. Wood and C. K. Yap, "The orthogonal convex skull problem," <i>Discr. Comput. Geom.</i>, vol. 3, no. 4, pp. 349-365, 1988.
• 328: {328} c. Arcelli and G. Sanniti de Baja, "Polygonal covering and concavity tree of binary digital pictures," in <i>Advances in Measurement and Control, MECO'78, Int. Symp. Measurement and Control </i>, M. H. Hamza and S. G. Tzafestas, Eds., Athens, Panhellenic Soc. Mech. Elec. Eng., June 1978, pp, 292-297.
• 329: F. Aurenhammer, On-line sorting of twisted sequences in linear time, BIT, v.28 n.2, p.194-204, February 1988 [doi>10.1007/BF01934085]
• 330: {330} J. Bajon, M. Cattoën, and S. D. Kim, "A concavity characterization method for digital objects," <i>Signal Processing</i>, vol. 9, no. 3, pp. 151-161, Oct. 1985.
• 331: {331} B. G. Batchelor, "Shape description using concavity trees," in <i>Advances in Measurement and Control, MECO'78, Int. Symp. Measurement and Control</i>, M. H. Hamza and S. G. Tzafestas, Eds. Athens, Panhellenic Soc. Mech. Elec. Eng., June 1978, pp. 385- 390.
• 332: {332} B. G. Batchelor, "Using concavity trees for shape description, "<i>IEE J. Comput. Digital Techniques</i>, vol. 2, no. 4, pp. 157-168, Aug. 1979
• 333: {333} B. G. Batchelor, "Hierarchical shape description based upon convex hulls of concavities, <i>J. Cybern.</i>, vol. 10, pp. 205-210, 1980.
• 334: {334} B. G. Batchelor, "Shape descriptors for labelling concavity trees," <i>J. Cybern. </i>, vol. 10, pp. 233-237, 1980.
• 335: {335} C. E. Blair and R. G. Jeroslow, "Extension of a theorem of Balas," <i>Discr. Appl. Math.</i>, vol. 9, no. 1, pp. 11-26, Sept. 1984.
• 336: {336} K. Q. Brown, "Voronoi diagrams from convex hulls," <i>Inform. Processing Lett.</i>, vol. 9, no. 5, pp. 223-228, Dec. 1979.
• 337: {337} L. Calabi and W. E. Hartnett, "Shape recognition, prairie fires, convex deficiencies and skeletons," <i>Amer. Math. Monthly</i>, vol. 75, pp. 335-342, 1968.
• 338: {338} J. M. Chassery and C. Garbay, "Iterative process for colour image segmentation using a convexity criterion," in <i>Applications of Digital Image Processing</i>, A. Oosterlinck and A. G. Tescher, Eds; <i>Proc. SPIE</i>, vol. 397, pp. 165-172, 1983.
• 339: {339} H. Edelsbrunner and J. W. Jaromczyk, "How ofeen can you see yourself in a convex configuration of mirrors?" in <i>Proc. 17th Southeastern Int. Conf. Combinatorics, Graph Theory, Computing </i>, Boca Raton, FL; <i>Congr. Numer.</i>, vol. 53, pp. 193-200, 1986.
• 340: {340} H. Edelsbrunner, D. G. Kirkpatrick, and R. Seidel, "On the shape of a set of points in the plane," <i>IEEE Trans. Inform. Theory</i>, vol. IT-29, no. 4, pp. 551-559, July 1983.
• 341: {341} R. J. Gardner, "Symmetrals and X-rays of planar convex bodies," <i>Arch. Math.</i>, vol. 41, pp. 183-189, 1983.
• 342: {342} V. Di Gesu, and M. C. Maccarone, "Description of fuzzy images by convex hull techniques," in <i>Proc. 8th ICPR</i>, Oct. 1986, pp. 1276-1278.
• 343: R. N. Goldman , Tony D. Derose, Recursive subdivision without the convex hull property, Computer Aided Geometric Design, v.3 n.4, p.247-265, 1987 [doi>10.1016/0167-8396(86)90002-6]
• 344: {344} H. P. A. Haas, E. Backer, and I. J. Boxma, "Convex hull nearest neighbor rule," in <i>Proc. 5th. ICPR</i>, Dec. 1980, pp. 87-90.
• 345: {345} M. Jourlin and B. Laget, "Convexity and symmetry: Part 1," in <i>Image Analysis and Mathematical Morphology, Volume 2: Theoretical Advances</i>, J. Serra, Ed. London: Academic, 1988, pp. 343-357.
• 346: {346} V. Klee, "On the complexity of <i>d</i>-dimensional Voronoi diagrams," <i>Arch. Math.</i>, vol. 34, pp. 75-80, 1980.
• 347: {347} R. A. Jarvis, "Computing the shape hull of point in the plane," in <i>Proc. IEEE Comput. Conf. Pattern Recognition Image Processing </i>, 1977, pp. 231-241.
• 348: Mirko Krivánek , Jaroslav Morávek, Clustering to minimize the sum of volumes of convex hulls of clusters is NP-complete, Fundamentals of Computation Theory, p.234-241, September 09-13, 1985
• 349: {349} G. Matheron and J. Serra, "Convexity and symmetry: Part 2," in <i>Image Analysis and Mathematical Morphology, Volume 2: Theoretical Advances</i>, J. Serra, Ed. London: Academic, 1988, pp. 359-375.
• 350: {350} L. O'Gorman and A. C. Sanderson, "The wedge filter technique for convex boundary estimation," <i>IEEE Trans. Pattern Anal. Machine Intell.</i>, vol. PAMI-7, no. 3, pp. 326-332, May 1985.
• 351: Panos M. Pardalos, Quadratic problems defined on a convex hull of points, BIT, v.28 n.2, p.323-329, February 1988 [doi>10.1007/BF01934095]
• 352: J Pecht, On the index of concavity of neighbourhood templates, Acta Cybernetica, v.7 n.4, p.373-376, August 1986
• 353: Jim Piper , Erik Granum, Computing distance transformations in convex and non-convex domains, Pattern Recognition, v.20 n.6, p.599-615, November 1, 1987 [doi>10.1016/0031-3203(87)90030-6]
• 354: {354} A. Rosenfeld and P. De La Torre, "Histogram concavity analysis as an aid in threshold selection," <i>IEEE Trans. Systems, Man. Cybern. </i>, vol. SMC-13, no. 3, pp. 231-235, Mar.-Apr. 1983.
• 355: {355} G. T. Toussaint, "The convex hull as a tool in pattern recognition," in <i>Proc. AFOSR Workshop Communication Theory and Applications </i>, Provincetown, MA, Sept. 1978, pp. 43-46.
• 356: {356} G. T. Toussaint, "On the application of the convex hull to histogram analysis in threshold selection," <i>Pattern Recognition Lett</i>, vol. 2, no. 2, pp. 75-77, Dec. 1983.
• 357: {357} P. Zamperoni, "Analysis and synthesis of binary images by means of convex blobs," in <i>Proc. Int. Conf. Digital Signal Processing</i>, Florence, Italy, Aug.-Sept. 1978, pp. 181-188.
• 358: Piero Zamperoni, Bilddarstellung durch konvexe Elementarmuster, Bildverarbeitung und Mustererkennung, DAGM Symposium, p.145-154, October 11-13, 1978
• 359: {359} P. Zamperoni, "Sequential growth of convex regions for grey-scale image analysis," in <i>Proc. 6th ICPR</i>, Oct. 1982, pp. 912-914.
• 360: V. Boltjansky , I. T. Gohberg, Results and problems in combinatorial geometry, Cambridge University Press, New York, NY, 1985
• 361: {361} A. Brønsted, <i>An Introduction to Convex Polytopes</i> (Graduate Texts in Mathematics, Vol. 90). Berlin: Springer-Verlag, 1983.
• 362: {362} H. S. M. Coxeter, <i>Regular Polytopes</i>. 2nd ed. New York: Dover, 1973.
• 363: {363} L. Danzer, B. Grünbaum, and V. Klee, "Helly's theorem and its relatives," in <i>Convexity, Proc. 7th Symp. Pure Math. Amer. Math. Soc.</i>, V. L. Klee, Ed., AMS, Providence, RI, 1963, pp. 101-180.
• 364: {364} B. Grünbaum, <i>Convex Polytopes</i>. New York: Wiley-Interscience, 1967.
• 365: {365} S. R. Lay, <i>Convex Sets and their Applications</i>. New York: Wiley, 1982.
• 366: {366} L. A. Lyusternik, <i>Convex Figures and Polyhedra</i>. New York: Dover, 1963.
• 367: {367} P. McMullen and G. C. Shephard, <i>Convex Polytopes and the Upper Bound Conjecture</i>. New York: Cambridge University Press, 1971.
• 368: {368} J. Stoer and C. Witzgall, <i>Convexity and Optimization in Finite Dimensions I</i>. Berlin: Springer-Verlag, 1970.
• 369: {369} H. S. Witsenhausen, "Some aspects of convexity useful in information theory," <i>IEEE Trans. Inform. Theory</i>, vol. IT-26, no. 3, pp. 265-271, May 1980.
• 370: {370} I. M. Yaglom and V. G. Boltyanskii, <i>Convex Figures</i>. New York: Holt, Rinehart & Winston, 1961.
• 371: Carlos A. Berenstein , Laveen N. Kanal , David Lavine , Eric C. Olson, A geometric approach to subpixel registration accuracy, Computer Vision, Graphics, and Image Processing, v.40 n.3, p.334-360, December 1, 1987 [doi>10.1016/S0734-189X(87)80146-9]
• 372: Carlos A. Berenstein , David Lavine, On the Number of Digital Straight Line Segments, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.6, p.880-887, November 1988 [doi>10.1109/34.9109]
• 373: M. E. Houle , G. T. Toussaint, Computing the Width of a Set, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.5, p.761-765, September 1988 [doi>10.1109/34.6790]
• 374: M. Reichling, On the detection of a common intersection of k convex objects in the plane, Information Processing Letters, v.29 n.1, p.25-29, Sept. 15, 1988 [doi>10.1016/0020-0190(88)90127-5]

INDEX TERMS

Primary Classification:
  A. General Literature

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
  I.4 IMAGE PROCESSING AND COMPUTER VISION
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Computer vision

General Terms:
Algorithms, Documentation

Keywords:
bibliography, computational complexity, computational convexity, computational geometry, computerised picture processing, convex hull, digital images, picture processing, straightness