{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T21:12:48Z","timestamp":1764364368404,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,12,6]],"date-time":"2018-12-06T00:00:00Z","timestamp":1544054400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004836","name":"Danish Council for Independent Research","doi-asserted-by":"crossref","award":["DFF-0602-02499B"],"award-info":[{"award-number":["DFF-0602-02499B"]}],"id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Center of Poland","award":["2015\/17\/D\/ST1\/00585"],"award-info":[{"award-number":["2015\/17\/D\/ST1\/00585"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,1,31]]},"abstract":"<jats:p>We provide a remarkably simple algorithm to compute all (at most four) common tangents of two disjoint simple polygons. Given each polygon as a read-only array of its corners in cyclic order, the algorithm runs in linear time and constant workspace and is the first to achieve the two complexity bounds simultaneously. The set of common tangents provides basic information about the convex hulls of the polygons\u2014whether they are nested, overlapping, or disjoint\u2014and our algorithm thus also decides this relationship.<\/jats:p>","DOI":"10.1145\/3284355","type":"journal-article","created":{"date-parts":[[2018,12,7]],"date-time":"2018-12-07T13:17:29Z","timestamp":1544188649000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Common Tangents of Two Disjoint Polygons in Linear Time and Constant Workspace"],"prefix":"10.1145","volume":"15","author":[{"given":"Mikkel","family":"Abrahamsen","sequence":"first","affiliation":[{"name":"University of Copenhagen, Copenhagen \u00d8, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bartosz","family":"Walczak","sequence":"additional","affiliation":[{"name":"Jagiellonian University, Krak\u00f3w, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,12,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"31st International Symposium on Computational Geometry (SoCG\u201915)","volume":"34","author":"Abrahamsen M.","year":"2015"},{"volume":"77","volume-title":"33rd International Symposium on Computational Geometry (SoCG\u201917)","author":"Abrahamsen M.","key":"e_1_2_1_2_1"},{"volume":"57","volume-title":"24th Annual European Symposium on Algorithms (ESA\u201916)","author":"Abrahamsen M.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","first-page":"46","article-title":"Constant-work-space algorithms for geometric problems","volume":"2","author":"Asano T.","year":"2011","journal-title":"J. Comput. Geom."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3232679.3232692"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9893-5"},{"volume-title":"43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201902)","author":"Brodal G. S.","key":"e_1_2_1_7_1"},{"volume-title":"30th IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201916)","author":"Carson E.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322235"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90041-X"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195991000025"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01994880"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1017"},{"volume":"955","volume-title":"4th International Workshop on Algorithms and Data Structures (WADS\u201995)","author":"Kirkpatrick D.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90086-X"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90012-X"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/359423.359430"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"volume-title":"IEEE Mediterranean Electrotechnical Conference (MELECON","year":"1983","author":"Toussaint G. T.","key":"e_1_2_1_19_1"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3284355","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3284355","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:43:49Z","timestamp":1750207429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3284355"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,6]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1,31]]}},"alternative-id":["10.1145\/3284355"],"URL":"https:\/\/doi.org\/10.1145\/3284355","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,12,6]]},"assertion":[{"value":"2018-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}