{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T19:14:19Z","timestamp":1779909259143,"version":"3.53.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,5,11]],"date-time":"2020-05-11T00:00:00Z","timestamp":1589155200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,5,11]],"date-time":"2020-05-11T00:00:00Z","timestamp":1589155200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Math Imaging Vis"],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s10851-020-00957-6","type":"journal-article","created":{"date-parts":[[2020,5,11]],"date-time":"2020-05-11T08:03:17Z","timestamp":1589184197000},"page":"693-703","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Efficiently Testing Digital Convexity and Recognizing Digital Convex Polygons"],"prefix":"10.1007","volume":"62","author":[{"given":"Lo\u00efc","family":"Crombez","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guilherme D. da","family":"Fonseca","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yan","family":"Gerard","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,5,11]]},"reference":[{"key":"957_CR1","volume-title":"Digital Geometry: Geometric Methods for Digital Picture Analysis","author":"R Klette","year":"2004","unstructured":"Klette, R., Rosenfeld, A.: Digital Geometry: Geometric Methods for Digital Picture Analysis. Elsevier, Amsterdam (2004)"},{"key":"957_CR2","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1109\/34.16713","volume":"11","author":"C Ronse","year":"1989","unstructured":"Ronse, C.: A bibliography on digital and computational convexity (1961\u20131988). IEEE Trans. Pattern Anal. Mach. Intell. 11, 181\u2013190 (1989)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"957_CR3","unstructured":"Minkowski, H., Zahlen, Geometrie der.: . No. vol. 2 in Geometrie der Zahlen, B.G. Teubner (1910)"},{"issue":"2","key":"957_CR4","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1109\/TPAMI.1982.4767221","volume":"4","author":"CE Kim","year":"1982","unstructured":"Kim, C.E., Rosenfeld, A.: Digital straight lines and convexity of digital regions. IEEE Trans. Pattern Anal. Mach. Intell. 4(2), 149\u2013153 (1982)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"6","key":"957_CR5","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1109\/TPAMI.1982.4767314","volume":"4","author":"CE Kim","year":"1982","unstructured":"Kim, C.E., Rosenfeld, A.: Convex digital solids. IEEE Trans. Pattern Anal. Mach. Intell. 4(6), 612\u2013618 (1982)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"3","key":"957_CR6","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1016\/S0734-189X(83)80047-4","volume":"21","author":"J-M Chassery","year":"1983","unstructured":"Chassery, J.-M.: Discrete convexity: definition, parametrization, and compatibility with continuous convexity. Comput. Vis. Graph. Image Process. 21(3), 326\u2013344 (1983)","journal-title":"Comput. Vis. Graph. Image Process."},{"issue":"2","key":"957_CR7","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1006\/cviu.1996.0022","volume":"63","author":"K Kishimoto","year":"1996","unstructured":"Kishimoto, K.: Characterizing digital convexity and straightness in terms of length and total absolute curvature. Comput. Vis. Image Underst. 63(2), 326\u2013333 (1996)","journal-title":"Comput. Vis. Image Underst."},{"issue":"12","key":"957_CR8","doi-asserted-by":"publisher","first-page":"2007","DOI":"10.1016\/S0031-3203(98)00065-X","volume":"31","author":"BB Chaudhuri","year":"1998","unstructured":"Chaudhuri, B.B., Rosenfeld, A.: On the computation of the digital convex hull and circular hull of a digital region. Pattern Recogn. 31(12), 2007\u20132016 (1998)","journal-title":"Pattern Recogn."},{"key":"957_CR9","doi-asserted-by":"crossref","unstructured":"Debled-Rennesson, I., R\u00e9my, J.-L., Rouyer-Degli, J.: Detection of the discrete convexity of polyominoes. Discrete Applied Mathematics, vol. 125, no. 1, pp. 115 \u2013 133, 2003. In: 9th International Conference on Discrete Geometry for Computer Imagery (DGCI 2000)","DOI":"10.1016\/S0166-218X(02)00227-5"},{"key":"957_CR10","doi-asserted-by":"crossref","unstructured":"Brlek, S., Lachaud, J.-O., Proven\u00e7al, X., Reutenauer, C.: Lyndon + Christoffel = digitally convex. Pattern Recognition, vol. 42, no. 10, pp. 2239\u20132246, 2009. Selected papers from the 14th IAPR International Conference on Discrete Geometry for Computer Imagery (2008)","DOI":"10.1016\/j.patcog.2008.11.010"},{"key":"957_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"MD Berg","year":"2008","unstructured":"Berg, M.D., Cheong, O., Kreveld, M.V., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Santa Clara (2008)","edition":"3"},{"key":"957_CR12","doi-asserted-by":"publisher","first-page":"780","DOI":"10.1145\/322276.322289","volume":"28","author":"AC-C Yao","year":"1981","unstructured":"Yao, A.C.-C.: A lower bound to finding convex hulls. J. ACM 28, 780\u2013787 (1981)","journal-title":"J. ACM"},{"key":"957_CR13","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1145\/359423.359430","volume":"20","author":"FP Preparata","year":"1977","unstructured":"Preparata, F.P., Hong, S.J.: Convex hulls of finite sets of points in two and three dimensions. Commun. ACM 20, 87\u201393 (1977)","journal-title":"Commun. ACM"},{"key":"957_CR14","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/BF02712873","volume":"16","author":"TM Chan","year":"1996","unstructured":"Chan, T.M.: Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete Comput. Geom. 16, 361\u2013368 (1996)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"957_CR15","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/0215021","volume":"15","author":"D Kirkpatrick","year":"1986","unstructured":"Kirkpatrick, D., Seidel, R.: The ultimate planar convex hull algorithm? SIAM J. Comput. 15(1), 287\u2013299 (1986)","journal-title":"SIAM J. Comput."},{"key":"957_CR16","first-page":"1899","volume":"47\u201348","author":"G Pick","year":"1899","unstructured":"Pick, G.: \u201cGeometrisches zur zahlenlehre,\u201d Sitzungsberichte des Deutschen Naturwissenschaftlich-Medicinischen Vereines f\u00fcr B\u00f6hmen \u201cLotos\u201d. Prag 47\u201348, 1899\u20131900 (1899)","journal-title":"Prag"},{"key":"957_CR17","unstructured":"Ehrhart, E.: Sur les polyd\u00e8res rationnels homoth\u00e9tiques \u00e0 n dimensions. Technical report, acad\u00e9mie des sciences, Paris (1962)"},{"issue":"4","key":"957_CR18","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1287\/moor.19.4.769","volume":"19","author":"AI Barvinok","year":"1994","unstructured":"Barvinok, A.I.: A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Math. Oper. Res. 19(4), 769\u2013779 (1994)","journal-title":"Math. Oper. Res."},{"key":"957_CR19","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/BF02574364","volume":"12","author":"AI Barvinok","year":"1994","unstructured":"Barvinok, A.I.: Computing the Ehrhart polynomial of a convex lattice polytope. Discrete Comput. Geom. 12, 35\u201348 (1994)","journal-title":"Discrete Comput. Geom."},{"issue":"16","key":"957_CR20","doi-asserted-by":"publisher","first-page":"3362","DOI":"10.1016\/j.dam.2009.04.022","volume":"157","author":"T Asano","year":"2009","unstructured":"Asano, T., Brimkov, V.E., Barneva, R.P.: Some theoretical challenges in digital geometry: a perspective. Discrete Appl. Math. 157(16), 3362\u20133371 (2009)","journal-title":"Discrete Appl. Math."},{"key":"957_CR21","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/S1571-0653(04)00496-2","volume":"12","author":"F Feschet","year":"2003","unstructured":"Feschet, F., Tougne, L.: On the min DSS problem of closed discrete curves. Electron. Notes Discrete Math. 12, 325\u2013336 (2003)","journal-title":"Electron. Notes Discrete Math."},{"key":"957_CR22","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1109\/TPAMI.1982.4767315","volume":"4","author":"CE Kim","year":"1982","unstructured":"Kim, C.E.: Digital convexity, straightness, and convex polygons. IEEE Trans. Pattern Anal. Mach. Intell. 4, 618\u2013626 (1982)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"957_CR23","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/978-3-319-32360-2_32","volume-title":"Discrete Geometry for Computer Imagery","author":"Y G\u00e9rard","year":"2016","unstructured":"G\u00e9rard, Y.: Recognition of digital polyhedra with a fixed number of faces. In: Normand, N., Gu\u00e9don, J., Autrusseau, F. (eds.) Discrete Geometry for Computer Imagery, pp. 415\u2013426. Springer International Publishing, Cham (2016)"},{"key":"957_CR24","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/s10851-017-0711-y","volume":"59","author":"Y Gerard","year":"2017","unstructured":"Gerard, Y.: About the decidability of polyhedral separability in the lattice $$\\mathbb{Z}^d$$. J. Math. Imaging Vis. 59, 52\u201368 (2017)","journal-title":"J. Math. Imaging Vis."},{"key":"957_CR25","doi-asserted-by":"crossref","unstructured":"G\u00e9rard, Y.: Recognition of digital polyhedra with a fixed number of faces is decidable in dimension 3. In: Proceedings of Discrete Geometry for Computer Imagery\u201420th IAPR International Conference, DGCI 2017, Vienna, Austria, September 19\u201321, 2017, pp. 279\u2013290 (2017)","DOI":"10.1007\/978-3-319-66272-5_23"},{"key":"957_CR26","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-030-14085-4_32","volume-title":"Discrete Geometry for Computer Imagery","author":"L Crombez","year":"2019","unstructured":"Crombez, L., da Fonseca, G.D., G\u00e9rard, Y.: Efficient algorithms to test digital convexity. In: Couprie, M., Cousty, J., Kenmochi, Y., Mustafa, N. (eds.) Discrete Geometry for Computer Imagery, pp. 409\u2013419. Springer International Publishing, Cham (2019)"},{"issue":"2","key":"957_CR27","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1017\/S0004972700030094","volume":"45","author":"CJ Colbourn","year":"1992","unstructured":"Colbourn, C.J., Simpson, R.: A note on bounds on the minimum area of convex lattice polygons. Bull. Aust. Math. Soc. 45(2), 237\u2013240 (1992)","journal-title":"Bull. Aust. Math. Soc."},{"issue":"4","key":"957_CR28","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1112\/S0024609398004482","volume":"30","author":"J \u017duni\u0107","year":"1998","unstructured":"\u017duni\u0107, J.: Notes on optimal convex lattice polygons. Bull. Lond. Math. Soc. 30(4), 377\u2013385 (1998)","journal-title":"Bull. Lond. Math. Soc."},{"key":"957_CR29","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1145\/235815.235821","volume":"22","author":"CB Barber","year":"1996","unstructured":"Barber, C.B., Dobkin, D.P., Huhdanpaa, H.: The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. 22, 469\u2013483 (1996)","journal-title":"ACM Trans. Math. Softw."},{"key":"957_CR30","unstructured":"Greenfield, J.S.: A proof for a quickhull algorithm. Technical report, Syracuse University (1990)"},{"issue":"1","key":"957_CR31","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N Megiddo","year":"1984","unstructured":"Megiddo, N.: Linear programming in linear time when the dimension is fixed. JACM 31(1), 114\u2013127 (1984)","journal-title":"JACM"},{"issue":"3","key":"957_CR32","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0890-5401(88)90049-1","volume":"77","author":"H Edelsbrunner","year":"1988","unstructured":"Edelsbrunner, H., Preparata, F.: Minimum polygonal separation. Inf. Comput. 77(3), 218\u2013232 (1988)","journal-title":"Inf. Comput."},{"issue":"1\u20133","key":"957_CR33","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.dam.2003.08.003","volume":"139","author":"D Coeurjolly","year":"2004","unstructured":"Coeurjolly, D., G\u00e9rard, Y., Reveill\u00e8s, J., Tougne, L.: An elementary algorithm for digital arc segmentation. Discrete Appl. Math. 139(1\u20133), 31\u201350 (2004)","journal-title":"Discrete Appl. Math."},{"key":"957_CR34","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1007\/978-3-642-19867-0_26","volume-title":"Discrete Geometry for Computer Imagery","author":"T Roussillon","year":"2011","unstructured":"Roussillon, T., Lachaud, J.-O.: Delaunay properties of digital straight segments. In: Debled-Rennesson, I., Domenjoud, E., Kerautret, B., Even, P. (eds.) Discrete Geometry for Computer Imagery, pp. 308\u2013319. Springer, Berlin (2011)"},{"key":"957_CR35","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1090\/S0002-9947-1963-0143105-7","volume":"106","author":"GE Andrews","year":"1963","unstructured":"Andrews, G.E.: A lower bound for the volumes of strictly convex bodies with many boundary points. Trans. Am. Math. Soc. 106, 270\u2013279 (1963)","journal-title":"Trans. Am. Math. Soc."},{"key":"957_CR36","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1090\/conm\/453\/08796","volume":"453","author":"I B\u00e1r\u00e1ny","year":"2008","unstructured":"B\u00e1r\u00e1ny, I.: Extremal problems for convex lattice polytopes: a survey. Contemp. Math. 453, 87\u2013103 (2008)","journal-title":"Contemp. Math."}],"container-title":["Journal of Mathematical Imaging and Vision"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10851-020-00957-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10851-020-00957-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10851-020-00957-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,11]],"date-time":"2021-05-11T00:33:05Z","timestamp":1620693185000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10851-020-00957-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,11]]},"references-count":36,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["957"],"URL":"https:\/\/doi.org\/10.1007\/s10851-020-00957-6","relation":{},"ISSN":["0924-9907","1573-7683"],"issn-type":[{"value":"0924-9907","type":"print"},{"value":"1573-7683","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,11]]},"assertion":[{"value":"8 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}