{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T15:40:17Z","timestamp":1772466017177,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T00:00:00Z","timestamp":1761868800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T00:00:00Z","timestamp":1761868800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["NSF DMS-2154347"],"award-info":[{"award-number":["NSF DMS-2154347"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>A fundamental question is whether one can maintain a maximum independent set in polylogarithmic update time for a dynamic collection of geometric objects in Euclidean space. Already, for a set of intervals, it is known that no dynamic algorithm can maintain an exact maximum independent set in sublinear update time. Therefore, the typical objective is to explore the trade-off between update time and solution size. Substantial efforts have been made in recent years to understand this question for various families of geometric objects, such as intervals, hypercubes, hyperrectangles, and fat objects.<\/jats:p>\n                  <jats:p>\n                    We present the first fully dynamic approximation algorithm for disks of arbitrary radii in the plane that maintains a constant-factor approximate maximum independent set in polylogarithmic expected amortized update time. Moreover, for a fully dynamic set of\n                    <jats:italic>n<\/jats:italic>\n                    disks of unit radius in the plane, we show that a 12-approximate maximum independent set can be maintained with worst-case update time\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(\\log 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:mo>log<\/mml:mo>\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                    , and optimal output-sensitive reporting. This result generalizes to fat objects of comparable sizes in any fixed dimension\n                    <jats:italic>d<\/jats:italic>\n                    , where the approximation ratio depends on the dimension and the fatness parameter. Further, we note that, even for a dynamic set of disks of unit radius in the plane, it is impossible to maintain\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(1+\\varepsilon )$$<\/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:mn>1<\/mml:mn>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mi>\u03b5<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -approximate maximum independent set in truly sublinear update time, under standard complexity assumptions.\n                  <\/jats:p>\n                  <jats:p>Our results build on two recent technical tools: (i) The MIX algorithm by Cardinal et al. (2021) that can smoothly transition from one independent set to another; hence it suffices to maintain a family of independent sets where the largest one is a constant-factor approximation of a maximum independent set. (ii) A dynamic nearest\/farthest neighbor data structure for disks by Kaplan et al. (2020) and Liu (2022), which generalizes the dynamic convex hull data structure by Chan (2010), and allows us to quickly find a \u201creplacement\u201d disk (if any) when a disk in one of our independent sets is deleted.<\/jats:p>","DOI":"10.1007\/s00454-025-00793-8","type":"journal-article","created":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T17:37:34Z","timestamp":1761932254000},"page":"391-430","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fully Dynamic Maximum Independent Sets of Disks in Polylogarithmic Update Time"],"prefix":"10.1007","volume":"75","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0104-1659","authenticated-orcid":false,"given":"Sujoy","family":"Bhore","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0454-3937","authenticated-orcid":false,"given":"Martin","family":"N\u00f6llenburg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8769-3190","authenticated-orcid":false,"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9314-8260","authenticated-orcid":false,"given":"Jules","family":"Wulms","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,10,31]]},"reference":[{"key":"793_CR1","doi-asserted-by":"publisher","unstructured":"Agarwal, P.K., van Kreveld, M., Suri, S.: Label placement by maximum independent set in rectangles. Comput. Geom. 11(3\u20134), 209\u2013218 (1998). https:\/\/doi.org\/10.1016\/S0925-7721(98)00028-5","DOI":"10.1016\/S0925-7721(98)00028-5"},{"issue":"2","key":"793_CR2","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.jalgor.2003.10.001","volume":"52","author":"J Alber","year":"2004","unstructured":"Alber, J., Fiala, J.: Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. J. Algorithms 52(2), 134\u2013151 (2004). https:\/\/doi.org\/10.1016\/j.jalgor.2003.10.001","journal-title":"J. Algorithms"},{"key":"793_CR3","doi-asserted-by":"publisher","DOI":"10.1142\/8685","author":"F Aurenhammer","year":"2013","unstructured":"Aurenhammer, F., Klein, R., Lee, D.-T.: Voronoi Diagrams and Delaunay Triangulations. World Sci. (2013). https:\/\/doi.org\/10.1142\/8685","journal-title":"World Sci."},{"issue":"1","key":"793_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539703437843","volume":"36","author":"R Bar-Yehuda","year":"2006","unstructured":"Bar-Yehuda, R., Halld\u00f3rsson, M.M., Naor, J., Shachnai, H., Shapira, I.: Scheduling split intervals. SIAM J. Comput. 36(1), 1\u201315 (2006). https:\/\/doi.org\/10.1137\/S0097539703437843","journal-title":"SIAM J. Comput."},{"key":"793_CR5","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s002240000113","volume":"32","author":"P Berman","year":"1999","unstructured":"Berman, P., Fujito, T.: On approximation properties of the independent set problem for low degree graphs. Theory Comput. Syst. 32, 115\u2013132 (1999). https:\/\/doi.org\/10.1007\/s002240000113","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"793_CR6","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1006\/jagm.2001.1188","volume":"41","author":"P Berman","year":"2001","unstructured":"Berman, P., DasGupta, B., Muthukrishnan, S., Ramaswami, S.: Efficient approximation algorithms for tiling and packing problems with rectangles. J. Algorithms 41(2), 443\u2013470 (2001). https:\/\/doi.org\/10.1006\/jagm.2001.1188","journal-title":"J. Algorithms"},{"key":"793_CR7","unstructured":"Bhore, S., Cardinal, J., Iacono, J., Koumoutsos, G.: Dynamic geometric independent set. In: Abstracts of 23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games (TJDCG), (2021). arXiv:2007.08643"},{"key":"793_CR8","doi-asserted-by":"publisher","unstructured":"Bhore, S., Chan, T.M.: Dynamic independent set of disks (and hypercubes) made easier. In: Proc. 2025 SIAM Symposium on Simplicity in Algorithms (SOSA), pp. 485\u2013495, (2025). https:\/\/doi.org\/10.1137\/1.9781611978315.3","DOI":"10.1137\/1.9781611978315.3"},{"key":"793_CR9","doi-asserted-by":"publisher","unstructured":"Bhore, S., Chan, T.M.: Fast static and dynamic approximation algorithms for geometric optimization problems: Piercing, independent set, vertex cover, and matching. In: Proc. 36th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2357\u20132386, (2025). https:\/\/doi.org\/10.1137\/1.9781611978322.79","DOI":"10.1137\/1.9781611978322.79"},{"key":"793_CR10","doi-asserted-by":"publisher","unstructured":"Bhore, S., Klute, F., Oostveen, J.J.: On streaming algorithms for geometric independent set and clique. In: Proc. 20th International Workshop on Approximation and Online Algorithms (WAOA), volume 13538 of LNCS, pp. 211\u2013224. Springer, (2022). https:\/\/doi.org\/10.1007\/978-3-031-18367-6_11","DOI":"10.1007\/978-3-031-18367-6_11"},{"issue":"1","key":"793_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3514240","volume":"27","author":"S Bhore","year":"2022","unstructured":"Bhore, S., Li, G., N\u00f6llenburg, M.: An algorithmic study of fully dynamic independent sets for map labeling. ACM J. Experimental Algorithmics (JEA) 27(1), 1\u201336 (2022). https:\/\/doi.org\/10.1145\/3514240","journal-title":"ACM J. Experimental Algorithmics (JEA)"},{"key":"793_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800191","volume-title":"Advanced Data Structures","author":"P Brass","year":"2008","unstructured":"Brass, P.: Advanced Data Structures. Cambridge University Press (2008). https:\/\/doi.org\/10.1017\/CBO9780511800191"},{"key":"793_CR13","doi-asserted-by":"publisher","unstructured":"Cardinal, J., Iacono, J., Koumoutsos, G.: Worst-case efficient dynamic geometric independent set. In: Proc. 29th European Symposium on Algorithms (ESA), volume 204 of LIPIcs, pp. 25:1\u201325:15, Schloss Dagstuhl, (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.25","DOI":"10.4230\/LIPIcs.ESA.2021.25"},{"key":"793_CR14","doi-asserted-by":"publisher","unstructured":"Chalermsook, P., Walczak, B.: Coloring and maximum weight independent set of rectangles. In: Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 860\u2013868, (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.54","DOI":"10.1137\/1.9781611976465.54"},{"issue":"2","key":"793_CR15","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/S0196-6774(02)00294-8","volume":"46","author":"TM Chan","year":"2003","unstructured":"Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms 46(2), 178\u2013189 (2003). https:\/\/doi.org\/10.1016\/S0196-6774(02)00294-8","journal-title":"J. Algorithms"},{"issue":"3","key":"793_CR16","doi-asserted-by":"publisher","first-page":"16:1","DOI":"10.1145\/1706591.1706596","volume":"57","author":"TM Chan","year":"2010","unstructured":"Chan, T.M.: A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries. J. ACM 57(3), 16:1-16:15 (2010). https:\/\/doi.org\/10.1145\/1706591.1706596","journal-title":"J. ACM"},{"issue":"4","key":"793_CR17","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1007\/s00454-020-00229-5","volume":"64","author":"TM Chan","year":"2020","unstructured":"Chan, T.M.: Dynamic geometric data structures via shallow cuttings. Discret. Comput. Geom. 64(4), 1235\u20131252 (2020). https:\/\/doi.org\/10.1007\/s00454-020-00229-5","journal-title":"Discret. Comput. Geom."},{"issue":"2","key":"793_CR18","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00454-012-9417-5","volume":"48","author":"TM Chan","year":"2012","unstructured":"Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. Discret. Comput. Geom. 48(2), 373\u2013392 (2012). https:\/\/doi.org\/10.1007\/s00454-012-9417-5","journal-title":"Discret. Comput. Geom."},{"issue":"1\u20133","key":"793_CR19","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"BN Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discret. Math. 86(1\u20133), 165\u2013177 (1990). https:\/\/doi.org\/10.1016\/0012-365X(90)90358-O","journal-title":"Discret. Math."},{"key":"793_CR20","doi-asserted-by":"publisher","unstructured":"Compton, S., Mitrovic, S., Rubinfeld, R.: New partitioning techniques and faster algorithms for approximate interval scheduling. In: Proc. 50th International Colloquium on Automata, Languages, and Programming (ICALP), volume 261 of LIPIcs, pp. 45:1\u201345:16. Schloss Dagstuhl, (2023). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2023.45","DOI":"10.4230\/LIPIcs.ICALP.2023.45"},{"key":"793_CR21","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2022.101976","volume":"111","author":"S de Berg","year":"2023","unstructured":"de Berg, S., Staals, F.: Dynamic data structures for $$k$$-nearest neighbor queries. Comput. Geom. 111, 101976 (2023). https:\/\/doi.org\/10.1016\/j.comgeo.2022.101976","journal-title":"Comput. Geom."},{"issue":"4","key":"793_CR22","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0925-7721(99)00059-0","volume":"15","author":"A Efrat","year":"2000","unstructured":"Efrat, A., Katz, M.J., Nielsen, F., Sharir, M.: Dynamic data structures for fat objects and their applications. Comput. Geom. 15(4), 215\u2013227 (2000). https:\/\/doi.org\/10.1016\/S0925-7721(99)00059-0","journal-title":"Comput. Geom."},{"issue":"6","key":"793_CR23","doi-asserted-by":"publisher","first-page":"1302","DOI":"10.1137\/S0097539702402676","volume":"34","author":"T Erlebach","year":"2005","unstructured":"Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Computing 34(6), 1302\u20131323 (2005). https:\/\/doi.org\/10.1137\/S0097539702402676","journal-title":"SIAM J. Computing"},{"key":"793_CR24","doi-asserted-by":"publisher","unstructured":"G\u00e1lvez, W., Khan, A., Mari, M., M\u00f6mke, T., Pittu, M.R., Wiese, A.: A 3-approximation algorithm for maximum independent set of rectangles. In: Proc. 32rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 894\u2013905, (2022). https:\/\/doi.org\/10.1137\/1.9781611977073.38","DOI":"10.1137\/1.9781611977073.38"},{"key":"793_CR25","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/j.tcs.2014.09.046","volume":"562","author":"A Gavruskin","year":"2015","unstructured":"Gavruskin, A., Khoussainov, B., Kokho, M., Liu, J.: Dynamic algorithms for monotonic interval scheduling problem. Theoret. Comput. Sci. 562, 227\u2013242 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2014.09.046","journal-title":"Theoret. Comput. Sci."},{"key":"793_CR26","doi-asserted-by":"crossref","unstructured":"Har-Peled, S: Geometric Approximation Algorithms, volume 173 of Mathematical Surveys and Monographs. AMS, (2011). URL: https:\/\/bookstore.ams.org\/surv-173\/","DOI":"10.1090\/surv\/173"},{"key":"793_CR27","doi-asserted-by":"publisher","unstructured":"Henzinger, M., Neumann, S., Wiese, A.: Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. In: Proc. 36th International Symposium on Computational Geometry (SoCG), volume 164 of LIPIcs, pp. 51:1\u201351:14, Schloss Dagstuhl, (2020). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2020.51","DOI":"10.4230\/LIPIcs.SoCG.2020.51"},{"issue":"1","key":"793_CR28","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32(1), 130\u2013136 (1985). https:\/\/doi.org\/10.1145\/2455.214106","journal-title":"J. ACM"},{"issue":"2","key":"793_CR29","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"HB Hunt III","year":"1998","unstructured":"Hunt, H.B., III., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. J. Algorithms 26(2), 238\u2013274 (1998). https:\/\/doi.org\/10.1006\/jagm.1997.0903","journal-title":"J. Algorithms"},{"issue":"3","key":"793_CR30","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1007\/s00454-020-00243-7","volume":"64","author":"H Kaplan","year":"2020","unstructured":"Kaplan, H., Mulzer, W., Roditty, L., Seiferth, P., Sharir, M.: Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. Discret. Comput. Geom. 64(3), 838\u2013904 (2020). https:\/\/doi.org\/10.1007\/s00454-020-00243-7","journal-title":"Discret. Comput. Geom."},{"key":"793_CR31","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds) Complexity of Computer Computations. The IBM Research Symposia Series. Springer, Boston, MA, (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"793_CR32","unstructured":"Khanna, S., Muthukrishnan, S., Paterson, M.: On approximating rectangle tiling and packing. In: Proc. 9th ACM-SIAM Symposium on Discrete algorithms (SODA), volume\u00a098, pp. 384\u2013393, (1998). https:\/\/dl.acm.org\/doi\/10.5555\/314613.314768"},{"key":"793_CR33","unstructured":"Kirchner, K., Wengerodt, G.: Die dichteste Packung von 36 Kreisen in einem Quadrat. Beitr\u00e4ge zur Algebra und Geometrie \/ Contributions to Algebra and Geometry 25, 147\u2013160 (1987). http:\/\/eudml.org\/doc\/138383"},{"issue":"3","key":"793_CR34","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1137\/20m1388371","volume":"51","author":"C-H Liu","year":"2022","unstructured":"Liu, C.-H.: Nearly optimal planar $$k$$ nearest neighbors queries under general distance functions. SIAM J. Comput. 51(3), 723\u2013765 (2022). https:\/\/doi.org\/10.1137\/20m1388371","journal-title":"SIAM J. Comput."},{"issue":"2","key":"793_CR35","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.3230250205","volume":"25","author":"MV Marathe","year":"1995","unstructured":"Marathe, M.V., Breu, H., Hunt, H.B., III., Ravi, S.S., Rosenkrantz, D.J.: Simple heuristics for unit disk graphs. Networks 25(2), 59\u201368 (1995). https:\/\/doi.org\/10.1002\/net.3230250205","journal-title":"Networks"},{"key":"793_CR36","doi-asserted-by":"publisher","unstructured":"Marx, D.: Efficient approximation schemes for geometric problems? In: Proc. 13th European Symposium on Algorithms (ESA), volume 3669 of LNCS, pp. 448\u2013459. Springer, (2005). https:\/\/doi.org\/10.1007\/11561071_41","DOI":"10.1007\/11561071_41"},{"key":"793_CR37","doi-asserted-by":"publisher","unstructured":"Marx, D.: On the optimality of planar and geometric approximation schemes. In: Proc. 48th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 338\u2013348, (2007). https:\/\/doi.org\/10.1109\/FOCS.2007.26","DOI":"10.1109\/FOCS.2007.26"},{"key":"793_CR38","doi-asserted-by":"publisher","unstructured":"Mitchell, J.S.B.: Approximating maximum independent set for rectangles in the plane. In: Proc. 62nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 339\u2013350, (2022). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00042","DOI":"10.1109\/FOCS52979.2021.00042"},{"key":"793_CR39","volume-title":"Davenport-Schinzel Sequences and their Geometric Applications","author":"M Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and their Geometric Applications. Cambridge University Press, Cambridge, England (1995)"},{"key":"793_CR40","doi-asserted-by":"publisher","unstructured":"Szab\u00f3, P.G., Specht, E.: Packing up to 200 equal circles in a square. In: Models and Algorithms for Global Optimization: Essays Dedicated to Antanas \u017dilinskas on the Occasion of His 60th Birthday, pages 141\u2013156. Springer, Boston, (2007). https:\/\/doi.org\/10.1007\/978-0-387-36721-7_9","DOI":"10.1007\/978-0-387-36721-7_9"},{"issue":"1","key":"793_CR41","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007). https:\/\/doi.org\/10.4086\/toc.2007.v003a006","journal-title":"Theory Comput."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-025-00793-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-025-00793-8","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-025-00793-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T14:49:36Z","timestamp":1772462976000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-025-00793-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,31]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["793"],"URL":"https:\/\/doi.org\/10.1007\/s00454-025-00793-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,31]]},"assertion":[{"value":"15 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 October 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 October 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}