{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T10:56:08Z","timestamp":1761389768659,"version":"build-2065373602"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"35","license":[{"start":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T00:00:00Z","timestamp":1745884800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T00:00:00Z","timestamp":1745884800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Multimed Tools Appl"],"DOI":"10.1007\/s11042-025-20856-5","type":"journal-article","created":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T06:02:05Z","timestamp":1745906525000},"page":"43453-43473","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A combinatorial algorithm for finding straight skeleton of a digital object"],"prefix":"10.1007","volume":"84","author":[{"given":"Anukul","family":"Maity","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2401-2885","authenticated-orcid":false,"given":"Mousumi","family":"Dutt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arindam","family":"Biswas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,4,29]]},"reference":[{"key":"20856_CR1","doi-asserted-by":"crossref","unstructured":"Kirkpatrick DG (1979) Efficient computation of continuous skeletons. In: Proceedings of the 20th Annual IEEE Symposium FOCS, IEEE, San Juan, PR, USA, pp 18\u201327","DOI":"10.1109\/SFCS.1979.15"},{"issue":"4","key":"20856_CR2","doi-asserted-by":"publisher","first-page":"620","DOI":"10.14733\/cadaps.2019.620-627","volume":"16","author":"M Held","year":"2018","unstructured":"Held M, Palfrader P (2018) Skeletal structures for modeling generalized chamfers and fillets in the presence of complex miters. Comput-Aided Des Appl 16(4):620\u2013627","journal-title":"Comput-Aided Des Appl"},{"key":"20856_CR3","doi-asserted-by":"crossref","unstructured":"Held M, Palfrader P (2017) Straight skeletons with additive and multiplicative weights and their application to the algorithmic generation of roofs and terrains. Comput Aided Des 92(C):33\u201341","DOI":"10.1016\/j.cad.2017.07.003"},{"issue":"2","key":"20856_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1944846.1944854","volume":"30","author":"T Kelly","year":"2011","unstructured":"Kelly T, Wonka P (2011) Interactive architectural modeling with procedural extrusions. ACM Trans Graph 30(2):1\u201315","journal-title":"ACM Trans Graph"},{"key":"20856_CR5","unstructured":"Blum H (1967) A transformation for extracting new descriptors of shape. In: Proceedings of the models for the perception of speech and visual form, MIT Press, Cambridge, pp 362\u2013380"},{"key":"20856_CR6","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1080\/00029890.1968.11970990","volume":"75","author":"L Calabi","year":"1968","unstructured":"Calabi L, Hartnett WE (1968) Shape recognition, prairie fires, convex deficiencies and skeletons. Am Math Mon 75:335\u2013342","journal-title":"Am Math Mon"},{"key":"20856_CR7","unstructured":"Vermeer PJ (1994) Medial axis transform to boundary representation conversion. PhD thesis, Purdue University, USA"},{"key":"20856_CR8","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF01200364","volume":"8","author":"HN G\u00fcrsoy","year":"1992","unstructured":"G\u00fcrsoy HN, Patrikalakis NM (1992) An automatic coarse and fine surface mesh generation scheme based on medial axis transform, part i: Algorithms. Engineering with Computers 8:121\u2013137","journal-title":"Engineering with Computers"},{"issue":"9","key":"20856_CR9","doi-asserted-by":"publisher","first-page":"1485","DOI":"10.1109\/5.163413","volume":"80","author":"V Srinivasan","year":"1992","unstructured":"Srinivasan V, Nackman LR, Tang JM, Meshkat SN (1992) Automatic mesh generation using the symmetric axis transformation of polygonal domains. Proc IEEE 80(9):1485\u20131501","journal-title":"Proc IEEE"},{"issue":"6","key":"20856_CR10","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1016\/0010-4485(95)00064-X","volume":"28","author":"A Sudhalkar","year":"1996","unstructured":"Sudhalkar A, G\u00fcrs\u00f6z L, Prinz F (1996) Box-skeletons of discrete solids. Comput Aided Des 28(6):507\u2013517","journal-title":"Comput Aided Des"},{"issue":"5","key":"20856_CR11","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/0961-3552(91)90035-3","volume":"13","author":"TKH Tam","year":"1991","unstructured":"Tam TKH, Armstrong CG (1991) 2d finite element mesh generation by medial axis subdivision. Adv Eng Softw Work 13(5):313\u2013324","journal-title":"Adv Eng Softw Work"},{"issue":"5","key":"20856_CR12","doi-asserted-by":"publisher","first-page":"982","DOI":"10.1145\/185675.185795","volume":"41","author":"JA Storer","year":"1994","unstructured":"Storer JA, Reif JH (1994) Shortest paths in the plane with polygonal obstacles. J ACM 41(5):982\u20131012","journal-title":"J ACM"},{"issue":"1","key":"20856_CR13","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/0196-6774(85)90021-5","volume":"6","author":"C \u00d3\u2019D\u00fanlaing","year":"1985","unstructured":"\u00d3\u2019D\u00fanlaing C, Yap CK (1985) A \u201cretraction\" method for planning the motion of a disc. J Algo 6(1):104\u2013111","journal-title":"J Algo"},{"issue":"4","key":"20856_CR14","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0010-4485(97)00071-7","volume":"30","author":"M Held","year":"1998","unstructured":"Held M (1998) Voronoi diagrams and offset curves of curvilinear polygons. Comput Aided Des 30(4):287\u2013300","journal-title":"Comput Aided Des"},{"issue":"3","key":"20856_CR15","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0010-4485(94)90042-6","volume":"26","author":"M Held","year":"1994","unstructured":"Held M, Lukacs G, Andor L (1994) Pocket machining based on contour-parallel tool paths generated by means of proximity maps. CAD Comput Aided Des 26(3):189\u2013203","journal-title":"CAD Comput Aided Des"},{"issue":"12","key":"20856_CR16","first-page":"752","volume":"1","author":"O Aichholzer","year":"1995","unstructured":"Aichholzer O, Aurenhammer F, Alberts D, G\u00e4rtner B (1995) A novel type of skeleton for polygons. J Univ Comput Sci 1(12):752\u2013761","journal-title":"J Univ Comput Sci"},{"issue":"2","key":"20856_CR17","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1111\/j.1467-8667.1993.tb00202.x","volume":"8","author":"A Recuero","year":"1993","unstructured":"Recuero A, Cuti\u00e9rrez JP (1993) Sloped roofs for architectural cad systems. Comput Aided Civ Infrastruct Eng 8(2):147\u2013159","journal-title":"Comput Aided Civ Infrastruct Eng"},{"key":"20856_CR18","doi-asserted-by":"crossref","unstructured":"Aichholzer O, Aurenhammer F (1996) Straight skeletons for general polygonal figures in the plane. In: Proceedings of the 2nd annual international conference on computing and combinatorics. COCOON \u201996, Springer, Berlin, Heidelberg, pp 117\u2013126","DOI":"10.1007\/3-540-61332-3_144"},{"key":"20856_CR19","doi-asserted-by":"crossref","unstructured":"Murase T, Sugihara K (2018) Automatic generation of 3-D building models by straight skeleton. In: Proceedings of the 14th IEEE international conference on signal processing. ICSP\u201918, Association for Computing Machinery, New York, NY, USA, pp 1040\u20131045","DOI":"10.1109\/ICSP.2018.8652493"},{"key":"20856_CR20","doi-asserted-by":"crossref","unstructured":"Lang RJ (1996) A computational algorithm for origami design. In: Proceedings of the 12th Annual symposium on computational geometry. SCG \u201996, Association for Computing Machinery, New York, NY, USA, pp 98\u2013105","DOI":"10.1145\/237218.237249"},{"key":"20856_CR21","doi-asserted-by":"crossref","unstructured":"Aichholzer O, Aurenhammer F, Palop B (2002) Quickest paths, straight skeletons, and the city voronoi diagram. In: Proceedings of the 18th annual symposium on computational geometry. SCG\u201902, Association for Computing Machinery, New York, NY, USA, pp 151\u2013159","DOI":"10.1145\/513400.513420"},{"key":"20856_CR22","doi-asserted-by":"crossref","unstructured":"Vigneron A, Yan L (2013) A faster algorithm for computing motorcycle graphs. In: Proceedings of the 29th annual symposium on computational geometry. SoCG\u201913, Association for Computing Machinery, New York, NY, USA, pp 17\u201326","DOI":"10.1145\/2493132.2462396"},{"key":"20856_CR23","doi-asserted-by":"crossref","unstructured":"Aichholzer O, Aurenhammer F (1996) Straight skeletons for general polygonal figures in the plane. In: Proceedings of the 2nd annual international conference on computing and combinatorics. COCOON \u201996, Springer, Berlin, Heidelberg, pp 117\u2013126","DOI":"10.1007\/3-540-61332-3_144"},{"key":"20856_CR24","doi-asserted-by":"crossref","unstructured":"Eppstein D, Erickson J (1998) Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions. In: Proceedings of the 14th annual symposium on computational geometry. SCG \u201998, Association for Computing Machinery, New York, NY, USA, pp 58\u201367","DOI":"10.1145\/276884.276891"},{"key":"20856_CR25","unstructured":"Felkel P, Obdrzalek S (1998) Straight skeleton implementation. In: Proceedings of the spring conference on computer graphics, pp 210\u2013218"},{"key":"20856_CR26","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/j.gmod.2013.03.005","volume":"75","author":"J Mart\u00ednez","year":"2013","unstructured":"Mart\u00ednez J, Garcia NP, Anglada MV (2013) Skeletal representations of orthogonal shapes. Graph Model 75:189\u2013207","journal-title":"Graph Model"},{"key":"20856_CR27","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1142\/S0218195919500080","volume":"29","author":"G Eder","year":"2019","unstructured":"Eder G, Held M, Palfrader P (2019) Recognizing geometric trees as positively weighted straight skeletons and reconstructing their input. Int J Comput Geom Appl 29:251\u2013267","journal-title":"Int J Comput Geom Appl"},{"key":"20856_CR28","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2021.101760","volume":"96","author":"G Eder","year":"2021","unstructured":"Eder G, Held M, Palfrader P (2021) Implementing straight skeletons with exact arithmetic: Challenges and experiences. Comput Geom 96:101760","journal-title":"Comput Geom"},{"key":"20856_CR29","first-page":"13","volume-title":"Eurographics 2010 - short papers","author":"J Martinez","year":"2010","unstructured":"Martinez J, Vigo M, Pla-Garcia N, Ayala D (2010) Skeleton computation of an image using a geometric approach. Eurographics 2010 - short papers. The Eurographics Association, Sweden, pp 13\u201316"},{"issue":"4","key":"20856_CR30","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/j.jvcir.2010.02.001","volume":"21","author":"A Biswas","year":"2010","unstructured":"Biswas A, Bhowmick P, Bhattacharya BB (2010) Construction of isothetic covers of a digital object: A combinatorial approach. J Vis Commun Image Represent 21(4):295\u2013310","journal-title":"J Vis Commun Image Represent"},{"key":"20856_CR31","doi-asserted-by":"crossref","unstructured":"Biswas A, Bhowmick P, Bhattacharya BB (2005) TIPS: on finding a tight isothetic polygonal shape covering a 2d object. In: Proceedings of the 14th scandinavian conference of image analysis (SCIA). Lecture Notes in Computer Science, vol 3540. Springer, Joensuu, Finland, pp 930\u2013939","DOI":"10.1007\/11499145_94"},{"key":"20856_CR32","volume-title":"Discrete and Comput Geom","author":"SL Devadoss","year":"2011","unstructured":"Devadoss SL, O\u2019Rourke J (2011) Discrete and Comput Geom. Princeton University Press, New Jersey"}],"container-title":["Multimedia Tools and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11042-025-20856-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11042-025-20856-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11042-025-20856-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T10:50:27Z","timestamp":1761389427000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11042-025-20856-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,29]]},"references-count":32,"journal-issue":{"issue":"35","published-online":{"date-parts":[[2025,10]]}},"alternative-id":["20856"],"URL":"https:\/\/doi.org\/10.1007\/s11042-025-20856-5","relation":{},"ISSN":["1573-7721"],"issn-type":[{"type":"electronic","value":"1573-7721"}],"subject":[],"published":{"date-parts":[[2025,4,29]]},"assertion":[{"value":"18 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 April 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Not applicable","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to publication"}}]}}