{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T21:09:01Z","timestamp":1766178541559,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,8,11]],"date-time":"2020-08-11T00:00:00Z","timestamp":1597104000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,8,11]],"date-time":"2020-08-11T00:00:00Z","timestamp":1597104000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100012774","name":"Innovation Fund Denmark","doi-asserted-by":"crossref","award":["DABAI"],"award-info":[{"award-number":["DABAI"]}],"id":[{"id":"10.13039\/100012774","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100008398","name":"VILLUM foundation","doi-asserted-by":"crossref","award":["16582"],"award-info":[{"award-number":["16582"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NWO","award":["614.001.504"],"award-info":[{"award-number":["614.001.504"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the following separation problem: Given a collection of pairwise disjoint coloured objects in the plane with<jats:italic>k<\/jats:italic>different colours, compute a shortest \u201cfence\u201d<jats:italic>F<\/jats:italic>, i.e., a union of curves of minimum total length, that separates every pair of objects of different colours. Two objects are separated if<jats:italic>F<\/jats:italic>contains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem as<jats:sc>geometric<\/jats:sc><jats:italic>k<\/jats:italic>-<jats:sc>cut<\/jats:sc>, as it is a geometric analog to the well-studied multicut problem on graphs. We first give an<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^4\\log ^3\\!n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:msup><mml:mi>n<\/mml:mi><mml:mn>4<\/mml:mn><\/mml:msup><mml:msup><mml:mo>log<\/mml:mo><mml:mn>3<\/mml:mn><\/mml:msup><mml:mspace\/><mml:mi>n<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colours with<jats:italic>n<\/jats:italic>corners in total. We then show that the problem is NP-hard for the case of three colours. Finally, we give a randomised<jats:inline-formula><jats:alternatives><jats:tex-math>$$4\/3\\cdot 1.2965$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mn>4<\/mml:mn><mml:mo>\/<\/mml:mo><mml:mn>3<\/mml:mn><mml:mo>\u00b7<\/mml:mo><mml:mn>1.2965<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation algorithm for polygons and any number of colours.<\/jats:p>","DOI":"10.1007\/s00454-020-00232-w","type":"journal-article","created":{"date-parts":[[2020,8,11]],"date-time":"2020-08-11T14:07:32Z","timestamp":1597154852000},"page":"575-607","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane"],"prefix":"10.1007","volume":"64","author":[{"given":"Mikkel","family":"Abrahamsen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panos","family":"Giannopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maarten","family":"L\u00f6ffler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0351-5945","authenticated-orcid":false,"given":"G\u00fcnter","family":"Rote","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,8,11]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Abrahamsen, M., Adamaszek, A., Bringmann, K., Cohen-Addad, V., Mehr, M., Rotenberg, E., Roytman, A., Thorup, M.: Fast fencing. In: 50th Annual ACM SIGACT Symposium on Theory of Computing (Los Angeles 2018), pp. 564\u2013573. ACM, New York (2018)","key":"232_CR1","DOI":"10.1145\/3188745.3188878"},{"unstructured":"Abrahamsen, M., Giannopoulos, P., L\u00f6ffler, M., Rote, G.: Geometric multicut. In: 46th International Colloquium on Automata, Languages, and Programming. Leibniz International Proceedings in Informatics, vol. 132, #\u00a09. Leibniz-Zent. Inform., Wadern (2019)","key":"232_CR2"},{"doi-asserted-by":"crossref","unstructured":"B\u00e9rczi, K., Chandrasekaran, K., Kir\u00e1ly, T., Madan, V.: Improving the integrality gap for multiway cut. In: Integer Programming and Combinatorial Optimization\u201420th International Conference. Lecture Notes in Comput. Sci., vol. 11480, pp. 115\u2013127. Springer, Cham (2019)","key":"232_CR3","DOI":"10.1007\/978-3-030-17953-3_9"},{"issue":"4","key":"232_CR4","doi-asserted-by":"publisher","first-page":"1280","DOI":"10.1137\/15M1042929","volume":"46","author":"G Borradaile","year":"2017","unstructured":"Borradaile, G., Klein, P.N., Mozes, S., Nussbaum, Y., Wulff-Nilsen, Ch.: Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time. SIAM J. Comput. 46(4), 1280\u20131303 (2017)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Schwartz, R., Weizman, B.: Simplex transformations and the multiway cut problem. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms (Barcelona 2017), pp. 2400\u20132410. SIAM, Philadelphia (2017)","key":"232_CR5","DOI":"10.1137\/1.9781611974782.158"},{"issue":"3","key":"232_CR6","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1006\/jcss.1999.1687","volume":"60","author":"G C\u0103linescu","year":"2000","unstructured":"C\u0103linescu, G., Karloff, H., Rabani, Y.: An improved approximation algorithm for MULTIWAY CUT. J. Comput. Syst. Sci. 60(3), 564\u2013574 (2000)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"232_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/147508.147511","volume":"39","author":"B Chazelle","year":"1992","unstructured":"Chazelle, B., Edelsbrunner, H.: An optimal algorithm for intersecting line segments in the plane. J. Assoc. Comput. Mach. 39(1), 1\u201354 (1992)","journal-title":"J. Assoc. Comput. Mach."},{"doi-asserted-by":"crossref","unstructured":"Chung, F.R.K., Graham, R.L.: A new bound for Euclidean Steiner minimal trees. In: Discrete Geometry and Convexity (New York 1982). Ann. New York Acad. Sci., vol. 440, pp. 328\u2013346. New York Acad. Sci., New York (1985)","key":"232_CR8","DOI":"10.1111\/j.1749-6632.1985.tb14564.x"},{"issue":"4","key":"232_CR9","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"issue":"9","key":"232_CR10","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1016\/0167-8655(93)90140-9","volume":"14","author":"P Eades","year":"1993","unstructured":"Eades, P., Rappaport, D.: The complexity of computing minimum separating polygons. Pattern Recogn. Lett. 14(9), 715\u2013718 (1993)","journal-title":"Pattern Recogn. Lett."},{"issue":"4","key":"232_CR11","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1137\/0132072","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: The complexity of computing Steiner minimal trees. SIAM J. Appl. Math. 32(4), 835\u2013859 (1977)","journal-title":"SIAM J. Appl. Math."},{"unstructured":"Gawrychowski, P., Karczmarz, A.: Improved bounds for shortest paths in dense distance graphs. In: 45th International Colloquium on Automata, Languages, and Programming. Leibniz International Proceedings in Informatics, vol. 107, #\u00a061. Leibniz-Zent. Inform., Wadern (2018)","key":"232_CR12"},{"key":"232_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0116001","volume":"16","author":"EN Gilbert","year":"1968","unstructured":"Gilbert, E.N., Pollak, H.O.: Steiner minimal trees. SIAM J. Appl. Math. 16, 1\u201329 (1968)","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"232_CR14","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1111\/j.2517-6161.1989.tb01764.x","volume":"51","author":"DM Greig","year":"1989","unstructured":"Greig, D.M., Porteous, B.T., Seheult, A.H.: Exact maximum a posteriori estimation for binary images. J. R. Stat. Soc. Ser. B (Methodological) 51(2), 271\u2013279 (1989)","journal-title":"J. R. Stat. Soc. Ser. B (Methodological)"},{"unstructured":"Hohenwarter, M., Borcherds, M., Ancsin, G., Bencze, B., Blossier, M., Delobelle, A., Denizet, C., \u00c9li\u00e1s, J., Fekete, A., G\u00e1l, L., Kone\u010dn\u00fd, Z., Kov\u00e1cs, Z., Lizelfelner, S., Parisse, B., Sturr, G.: GeoGebra\u00a05.0 (2018). http:\/\/www.geogebra.org","key":"232_CR15"},{"issue":"3","key":"232_CR16","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1287\/moor.1030.0086","volume":"29","author":"DR Karger","year":"2004","unstructured":"Karger, D.R., Klein, P., Stein, C., Thorup, M., Young, N.E.: Rounding algorithms for a geometric embedding of minimum multiway cut. Math. Oper. Res. 29(3), 436\u2013461 (2004)","journal-title":"Math. Oper. Res."},{"doi-asserted-by":"crossref","unstructured":"Kayal, N., Saha, C.: On the sum of square roots of polynomials and related problems. ACM Trans. Comput. Theory 4(4), #\u00a09 (2012)","key":"232_CR17","DOI":"10.1145\/2382559.2382560"},{"doi-asserted-by":"crossref","unstructured":"Manokaran, R., Naor, J., Raghavendra, P., Schwartz, R.: SDP gaps and UGC hardness for multiway cut, $$0$$-extension, and metric labeling. In: 40th Annual ACM Symposium on Theory of Computing (Victoria 2008), pp. 11\u201320. ACM, New York (2008)","key":"232_CR18","DOI":"10.1145\/1374376.1374379"},{"issue":"4","key":"232_CR19","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/197405.197408","volume":"26","author":"J Matou\u0161ek","year":"1994","unstructured":"Matou\u0161ek, J.: Geometric range searching. ACM Comput. Surv. 26(4), 422\u2013461 (1994)","journal-title":"ACM Comput. Surv."},{"doi-asserted-by":"crossref","unstructured":"Mulzer, W., Rote, G.: Minimum-weight triangulation is NP-hard. J. ACM 55(2), #\u00a011 (2008)","key":"232_CR20","DOI":"10.1145\/1346330.1346336"},{"doi-asserted-by":"crossref","unstructured":"Sharma, A., Vondr\u00e1k, J.: Multiway cut, pairwise realizable distributions, and descending thresholds. In: 46th Annual ACM Symposium on Theory of Computing (New York), pp. 724\u2013733. ACM, New York (2014)","key":"232_CR21","DOI":"10.1145\/2591796.2591866"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00232-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-020-00232-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00232-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,11]],"date-time":"2024-08-11T17:05:03Z","timestamp":1723395903000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-020-00232-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,11]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["232"],"URL":"https:\/\/doi.org\/10.1007\/s00454-020-00232-w","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2020,8,11]]},"assertion":[{"value":"7 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 March 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 July 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 August 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}