{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T04:32:02Z","timestamp":1777869122287,"version":"3.51.4"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T00:00:00Z","timestamp":1777507200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T00:00:00Z","timestamp":1777507200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100007655","name":"Czech Technical University in Prague","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007655","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We study a geometric facility location problem under imprecision. Given\n                    <jats:italic>n<\/jats:italic>\n                    unit segments on the real line, each with one of\n                    <jats:italic>k<\/jats:italic>\n                    colors, the goal is to place a point on each segment such that the resulting\n                    <jats:italic>minimum color-spanning interval<\/jats:italic>\n                    is as large as possible. A minimum color-spanning interval is an interval of minimum size that contains at least one point from a given segment of each color. We prove that if the input segments are pairwise disjoint, the problem can be solved in\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    ) time, even for segments of arbitrary length. For overlapping segments, the problem becomes much more difficult. Nevertheless, we show that it can be solved in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(n \\log ^2 n)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:msup>\n                              <mml:mo>log<\/mml:mo>\n                              <mml:mn>2<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    time when\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$k=2$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , by exploiting several structural properties of candidate solutions, combined with a number of advanced algorithmic techniques. Interestingly, this shows a sharp contrast with the 2-dimensional version of the problem, recently shown to be NP-hard.\n                  <\/jats:p>","DOI":"10.1007\/s00224-026-10270-1","type":"journal-article","created":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T13:10:33Z","timestamp":1777554633000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Computing Largest Minimum Color-Spanning Intervals of Imprecise Points"],"prefix":"10.1007","volume":"70","author":[{"given":"Ankush","family":"Acharyya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vahideh","family":"Keikha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria","family":"Saumell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rodrigo I.","family":"Silveira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,30]]},"reference":[{"key":"10270_CR1","doi-asserted-by":"crossref","unstructured":"Abellanas, M., Hurtado, F., Icking, C., Klein, R., Langetepe, E., Ma, L., Palop, B., Sacrist\u00e1n, V.: Smallest color-spanning objects. In: ESA, pp. 278\u2013289 (2001)","DOI":"10.1007\/3-540-44676-1_23"},{"issue":"5","key":"10270_CR2","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1142\/S0218195909003076","volume":"19","author":"S Das","year":"2009","unstructured":"Das, S., Goswami, P.P., Nandy, S.C.: Smallest color-spanning object revisited. Int. J. Comput. Geom. Appl. 19(5), 457\u2013478 (2009)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"2","key":"10270_CR3","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s00453-008-9174-2","volume":"56","author":"M L\u00f6ffler","year":"2010","unstructured":"L\u00f6ffler, M., Kreveld, M.: Largest and smallest convex hulls for imprecise points. Algorithmica 56(2), 235\u2013269 (2010)","journal-title":"Algorithmica"},{"issue":"4","key":"10270_CR4","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1016\/j.comgeo.2009.03.007","volume":"43","author":"M L\u00f6ffler","year":"2010","unstructured":"L\u00f6ffler, M., Kreveld, M.: Largest bounding box, smallest diameter, and related problems on imprecise points. Comput. Geom. 43(4), 419\u2013433 (2010)","journal-title":"Comput. Geom."},{"key":"10270_CR5","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/j.tcs.2022.07.016","volume":"930","author":"A Acharyya","year":"2022","unstructured":"Acharyya, A., Jallu, R.K., Keikha, V., L\u00f6ffler, M., Saumell, M.: Minimum color spanning circle of imprecise points. Theor. Comput. Sci. 930, 116\u2013127 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"10270_CR6","doi-asserted-by":"crossref","unstructured":"Khanteimouri, P., Mohades, A., Abam, M.A., Kazemi, M.R.: Computing the smallest color-spanning axis-parallel square. In: ISAAC, pp. 634\u2013643 (2013)","DOI":"10.1007\/978-3-642-45030-3_59"},{"key":"10270_CR7","unstructured":"Hasheminejad, J., Khanteimouri, P., Mohades, A.: Computing the smallest color spanning equilateral triangle. In: EuroCG, pp. 32\u201335 (2015)"},{"key":"10270_CR8","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.tcs.2017.11.031","volume":"725","author":"A Acharyya","year":"2018","unstructured":"Acharyya, A., Nandy, S.C., Roy, S.: Minimum width color spanning annulus. Theor. Comput. Sci. 725, 16\u201330 (2018)","journal-title":"Theor. Comput. Sci."},{"issue":"21\u201322","key":"10270_CR9","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.ipl.2011.07.015","volume":"111","author":"R Fleischer","year":"2011","unstructured":"Fleischer, R., Xu, X.: Computing minimum diameter color spanning sets is hard. Inf. Process. Lett. 111(21\u201322), 1054\u20131056 (2011)","journal-title":"Inf. Process. Lett."},{"key":"10270_CR10","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.tcs.2011.12.075","volume":"508","author":"DZ Chen","year":"2013","unstructured":"Chen, D.Z., Misio\u0142ek, E.: Algorithms for interval structures with applications. Theor. Comput. Sci. 508, 41\u201353 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"10270_CR11","unstructured":"Khanteimouri, P., Mohades, A., Abam, M.A., Kazemi, M.R.: Spanning colored points with intervals. In: CCCG, pp. 265\u2013270 (2013)"},{"key":"10270_CR12","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1016\/j.tcs.2015.01.039","volume":"609","author":"M Jiang","year":"2016","unstructured":"Jiang, M., Wang, H.: Shortest color-spanning intervals. Theor. Comput. Sci. 609, 561\u2013568 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"10270_CR13","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.dam.2018.02.014","volume":"280","author":"S Banerjee","year":"2020","unstructured":"Banerjee, S., Misra, N., Nandy, S.C.: Color spanning objects: Algorithms and hardness results. Discret. Appl. Math. 280, 14\u201322 (2020)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"10270_CR14","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/j.orl.2022.03.005","volume":"50","author":"R Hu","year":"2022","unstructured":"Hu, R., Zhang, J.: Computing k-centers of uncertain points on a real line. Oper. Res. Lett. 50(3), 310\u2013314 (2022)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"10270_CR15","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1137\/0210018","volume":"10","author":"MR Garey","year":"1981","unstructured":"Garey, M.R., Johnson, D.S., Simons, B.B., Tarjan, R.E.: Scheduling unit-time tasks with arbitrary release times and deadlines. SIAM J. Comput. 10(2), 256\u2013269 (1981)","journal-title":"SIAM J. Comput."},{"key":"10270_CR16","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.dam.2017.12.028","volume":"239","author":"S Li","year":"2018","unstructured":"Li, S., Wang, H.: Dispersing points on intervals. Discret. Appl. Math. 239, 106\u2013118 (2018)","journal-title":"Discret. Appl. Math."},{"key":"10270_CR17","doi-asserted-by":"crossref","unstructured":"Biedl, T., Lubiw, A., Naredla, A.M., Ralbovsky, P.D., Stroud, G.: Dispersion for intervals: A geometric approach. In: SOSA, pp. 37\u201344 (2021)","DOI":"10.1137\/1.9781611976496.4"},{"issue":"2","key":"10270_CR18","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1016\/j.dam.2004.02.018","volume":"145","author":"J Fiala","year":"2005","unstructured":"Fiala, J., Kratochv\u00edl, J., Proskurowski, A.: Systems of distant representatives. Discret. Appl. Math. 145(2), 306\u2013316 (2005)","journal-title":"Discret. Appl. Math."},{"key":"10270_CR19","unstructured":"Naredla, A.M.: Algorithms for geometric facility location: Centers in a polygon and dispersion on a line. PhD thesis, University of Waterloo (2023)"},{"key":"10270_CR20","doi-asserted-by":"crossref","unstructured":"Ray shooting into a fixed direction. In: Berg, M. (ed.) Ray Shooting, Depth Orders and Hidden Surface Removal, pp. 67\u201384. Springer, Berlin, Heidelberg (1993)","DOI":"10.1007\/BFb0029819"},{"issue":"3","key":"10270_CR21","first-page":"28","volume":"5","author":"Y Giyora","year":"2009","unstructured":"Giyora, Y., Kaplan, H.: Optimal dynamic vertical ray shooting in rectilinear planar subdivisions. ACM Trans. Algorithms 5(3), 28\u201312851 (2009)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"10270_CR22","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1137\/0214021","volume":"14","author":"EM McCreight","year":"1985","unstructured":"McCreight, E.M.: Priority search trees. SIAM J. Comput. 14(2), 257\u2013276 (1985)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10270_CR23","first-page":"45","volume":"9","author":"TM Chan","year":"2018","unstructured":"Chan, T.M., Tsakalidis, K.: Dynamic orthogonal range searching on the RAM, revisited. J. Comput. Geom. 9(2), 45\u201366 (2018)","journal-title":"J. Comput. Geom."},{"issue":"4","key":"10270_CR24","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1137\/0218055","volume":"18","author":"R Cole","year":"1989","unstructured":"Cole, R., Salowe, J.S., Steiger, W.L., Szemer\u00e9di, E.: An optimal-time algorithm for slope selection. SIAM J. Comput. 18(4), 792\u2013810 (1989)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10270_CR25","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0020-0190(93)90234-Z","volume":"47","author":"MJ Katz","year":"1993","unstructured":"Katz, M.J., Sharir, M.: Optimal slope selection via expanders. Inf. Process. Lett. 47(3), 115\u2013122 (1993)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"10270_CR26","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0925-7721(97)00025-4","volume":"10","author":"H Br\u00f6nnimann","year":"1998","unstructured":"Br\u00f6nnimann, H., Chazelle, B.: Optimal slope selection via cuttings. Comput. Geom. 10(1), 23\u201329 (1998)","journal-title":"Comput. Geom."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10270-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-026-10270-1","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10270-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T13:10:41Z","timestamp":1777554641000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-026-10270-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,30]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["10270"],"URL":"https:\/\/doi.org\/10.1007\/s00224-026-10270-1","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,30]]},"assertion":[{"value":"16 December 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 March 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 April 2026","order":3,"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 no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"31"}}