{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:04:37Z","timestamp":1767927877110,"version":"3.49.0"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030678982","type":"print"},{"value":"9783030678999","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-67899-9_14","type":"book-chapter","created":{"date-parts":[[2021,1,28]],"date-time":"2021-01-28T00:05:55Z","timestamp":1611792355000},"page":"179-195","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Worst-Case Optimal Algorithm to Compute the Minkowski Sum of Convex Polytopes"],"prefix":"10.1007","author":[{"given":"Sandip","family":"Das","sequence":"first","affiliation":[]},{"given":"Subhadeep Ranjan","family":"Dev","sequence":"additional","affiliation":[]},{"given":"Swami","family":"Sarvottamananda","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,1,28]]},"reference":[{"issue":"1","key":"14_CR1","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s10240-016-0083-7","volume":"124","author":"KA Adiprasito","year":"2016","unstructured":"Adiprasito, K.A., Sanyal, R.: Relative Stanley-Reisner theory and upper bound theorems for Minkowski sums. Publications math\u00e9matiques de l\u2019IH\u00c9S 124(1), 99\u2013163 (2016)","journal-title":"Publications math\u00e9matiques de l\u2019IH\u00c9S"},{"issue":"1\u20132","key":"14_CR2","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0925-7721(01)00041-4","volume":"21","author":"PK Agarwal","year":"2002","unstructured":"Agarwal, P.K., Flato, E., Halperin, D.: Polygon decomposition for efficient construction of Minkowski sums. Comput. Geom. 21(1\u20132), 39\u201361 (2002)","journal-title":"Comput. Geom."},{"key":"14_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/3-540-45545-0_71","volume-title":"Computational Science \u2014 ICCS 2001","author":"H Bekker","year":"2001","unstructured":"Bekker, H., Roerdink, J.B.T.M.: An efficient algorithm to calculate the Minkowski sum of convex 3D polyhedra. In: Alexandrov, V.N., Dongarra, J.J., Juliano, B.A., Renner, R.S., Tan, C.J.K. (eds.) ICCS 2001. LNCS, vol. 2073, pp. 619\u2013628. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-45545-0_71"},{"key":"14_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M de Berg","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-77974-2","edition":"3"},{"issue":"4","key":"14_CR5","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/BF02712874","volume":"16","author":"TM Chan","year":"1996","unstructured":"Chan, T.M.: Output-sensitive results on convex hulls, extreme points, and related problems. Discret. Comput. Geom. 16(4), 369\u2013387 (1996). https:\/\/doi.org\/10.1007\/BF02712874","journal-title":"Discret. Comput. Geom."},{"issue":"4","key":"14_CR6","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/BF02573985","volume":"10","author":"B Chazelle","year":"1993","unstructured":"Chazelle, B.: An optimal convex hull algorithm in any fixed dimension. Discret. Comput. Geom. 10(4), 377\u2013409 (1993). https:\/\/doi.org\/10.1007\/BF02573985","journal-title":"Discret. Comput. Geom."},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Chazelle, B.M.: Convex decompositions of polyhedra. In: Proceedings STOC, pp. 70\u201379 (1981)","DOI":"10.1145\/800076.802459"},{"key":"14_CR8","unstructured":"Chazelle, B.M., Dobkin, D.P.: Optimal convex decompositions. In: Toussaint, G.T. (ed.) Computational Geometry. Machine Intelligence and Pattern Recognition, vol. 2, pp. 63\u2013133 (1985)"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Chew, L.P., Scot Drysdale, R.L.: Voronoi diagrams based on convex distance functions. In: Proceedings SoCG, pp. 235\u2013244 (1985)","DOI":"10.1145\/323233.323264"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Das, S., Nandy, A., Sarvottamananda, S.: Radius, diameter, incenter, circumcenter, width and minimum enclosing cylinder for some polyhedral distance functions. Discret. Appl. Math. (2020, in press)","DOI":"10.1016\/j.dam.2020.10.021"},{"key":"14_CR11","series-title":"EATCS Monographs on Theoretical Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H Edelsbrunner","year":"1987","unstructured":"Edelsbrunner, H.: Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science. Springer, Heidelberg (1987). https:\/\/doi.org\/10.1007\/978-3-642-61568-9"},{"key":"14_CR12","doi-asserted-by":"crossref","unstructured":"Fogel, E., Halperin, D.: Exact Minkowski sums of convex polyhedra. In: Proceedings SoCG, pp. 382\u2013383 (2005)","DOI":"10.1145\/1064092.1064157"},{"issue":"4","key":"14_CR13","doi-asserted-by":"publisher","first-page":"1261","DOI":"10.1016\/j.jsc.2003.08.007","volume":"38","author":"K Fukuda","year":"2004","unstructured":"Fukuda, K.: From the zonotope construction to the Minkowski addition of convex polytopes. J. Symb. Comput. 38(4), 1261\u20131272 (2004)","journal-title":"J. Symb. Comput."},{"key":"14_CR14","unstructured":"Fukuda, K., Weibel, C.: Computing all faces of the Minkowski sum of V-polytopes. In: Proceedings of the 17th CCCG, pp. 253\u2013256 (2005)"},{"issue":"2","key":"14_CR15","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1137\/0406019","volume":"6","author":"P Gritzmann","year":"1993","unstructured":"Gritzmann, P., Sturmfels, B.: Minkowski addition of polytopes: computational complexity and applications to Gr\u00f6bner basis. SIAM J. Discret. Math. 6(2), 246\u2013269 (1993)","journal-title":"SIAM J. Discret. Math."},{"key":"14_CR16","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0019-9","volume-title":"Convex Polytopes","author":"B Gr\u00fcnbaum","year":"2003","unstructured":"Gr\u00fcnbaum, B., Kaibel, V., Klee, V., Ziegler, G.M.: Convex Polytopes. Graduate Texts in Mathematics. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-1-4613-0019-9"},{"key":"14_CR17","doi-asserted-by":"crossref","unstructured":"Karavelas, M.I., Tzanaki, E.: The maximum number of faces of the Minkowski sum of two convex polytopes. In: Proceedings SODA, pp. 11\u201328 (2012)","DOI":"10.1137\/1.9781611973099.2"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Le Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings ISSAC, pp. 296\u2013303 (2014)","DOI":"10.1145\/2608628.2608664"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Ramkumar, G.D.: An algorithm to compute the Minkowski sum outer-face of two simple polygons. In: Proceedings SoCG, pp. 234\u2013241 (1996)","DOI":"10.1145\/237218.237374"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Seidel, R.: Constructing higher-dimensional convex hulls at logarithmic cost per face. In: Proceedings STOC, pp. 404\u2013413 (1986)","DOI":"10.1145\/12130.12172"},{"issue":"3","key":"14_CR21","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/s00454-011-9385-1","volume":"47","author":"C Weibel","year":"2012","unstructured":"Weibel, C.: Maximal F-vectors of Minkowski sums of large numbers of polytopes. Discret. Comput. Geom. 47(3), 519\u2013537 (2012)","journal-title":"Discret. Comput. Geom."},{"key":"14_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1007\/11841036_73","volume-title":"Algorithms \u2013 ESA 2006","author":"R Wein","year":"2006","unstructured":"Wein, R.: Exact and efficient construction of planar Minkowski sums using the convolution method. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 829\u2013840. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11841036_73"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-67899-9_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,28]],"date-time":"2021-01-28T00:09:49Z","timestamp":1611792589000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-67899-9_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030678982","9783030678999"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-67899-9_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"28 January 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CALDAM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Algorithms and Discrete Applied Mathematics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rupnagar","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 February 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 February 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"caldam2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.iitrpr.ac.in\/caldam2021\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair and OCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"82","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"39","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"48% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2,8","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2,21","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}