[{"intvolume":"       388","fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2026.106","language":[{"iso":"eng"}],"oa":1,"scopus_import":"1","article_processing_charge":"Yes","author":[{"first_name":"Sarita","last_name":"De Berg","full_name":"De Berg, Sarita"},{"first_name":"Nynne Maria Foldager","full_name":"Bække, Nynne Maria Foldager","last_name":"Bække"},{"first_name":"Frida Astrup","full_name":"Eriksen, Frida Astrup","last_name":"Eriksen"},{"first_name":"Ivor","full_name":"Van Der Hoog, Ivor","last_name":"Van Der Hoog"},{"first_name":"Eva","full_name":"Rotenberg, Eva","last_name":"Rotenberg"},{"first_name":"Daniel P","id":"7397d908-b582-11f0-bf73-88b902e86527","full_name":"Rutschmann, Daniel P","last_name":"Rutschmann"}],"department":[{"_id":"MoHe"}],"OA_type":"gold","article_number":"106","ddc":["000"],"file_date_updated":"2026-09-16T08:58:04Z","volume":388,"oa_version":"Published Version","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2026-09-13T22:01:52Z","date_updated":"2026-09-16T08:59:49Z","type":"conference","month":"08","date_published":"2026-08-25T00:00:00Z","doi":"10.4230/LIPIcs.ESA.2026.106","arxiv":1,"external_id":{"arxiv":["2605.07523"]},"keyword":["Pareto front","imprecise geometry","instance optimality","universal optimality","preprocessing model","partial information"],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959774451"]},"researchdata_availability":"no","_id":"22916","quality_controlled":"1","publication":"34th Annual European Symposium on Algorithms","das_tickbox":"0","alternative_title":["LIPIcs"],"day":"25","citation":{"short":"S. De Berg, N.M.F. Bække, F.A. Eriksen, I. Van Der Hoog, E. Rotenberg, D.P. Rutschmann, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","ista":"De Berg S, Bække NMF, Eriksen FA, Van Der Hoog I, Rotenberg E, Rutschmann DP. 2026. Instance optimal and universally optimal bounds for imprecise pareto fronts. 34th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 106.","chicago":"De Berg, Sarita, Nynne Maria Foldager Bække, Frida Astrup Eriksen, Ivor Van Der Hoog, Eva Rotenberg, and Daniel P Rutschmann. “Instance Optimal and Universally Optimal Bounds for Imprecise Pareto Fronts.” In <i>34th Annual European Symposium on Algorithms</i>, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.106\">https://doi.org/10.4230/LIPIcs.ESA.2026.106</a>.","mla":"De Berg, Sarita, et al. “Instance Optimal and Universally Optimal Bounds for Imprecise Pareto Fronts.” <i>34th Annual European Symposium on Algorithms</i>, vol. 388, 106, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.106\">10.4230/LIPIcs.ESA.2026.106</a>.","apa":"De Berg, S., Bække, N. M. F., Eriksen, F. A., Van Der Hoog, I., Rotenberg, E., &#38; Rutschmann, D. P. (2026). Instance optimal and universally optimal bounds for imprecise pareto fronts. In <i>34th Annual European Symposium on Algorithms</i> (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.106\">https://doi.org/10.4230/LIPIcs.ESA.2026.106</a>","ieee":"S. De Berg, N. M. F. Bække, F. A. Eriksen, I. Van Der Hoog, E. Rotenberg, and D. P. Rutschmann, “Instance optimal and universally optimal bounds for imprecise pareto fronts,” in <i>34th Annual European Symposium on Algorithms</i>, L’Aquila, Italy, 2026, vol. 388.","ama":"De Berg S, Bække NMF, Eriksen FA, Van Der Hoog I, Rotenberg E, Rutschmann DP. Instance optimal and universally optimal bounds for imprecise pareto fronts. In: <i>34th Annual European Symposium on Algorithms</i>. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.106\">10.4230/LIPIcs.ESA.2026.106</a>"},"has_accepted_license":"1","publication_status":"published","file":[{"checksum":"75cfae9e9773be4b06f9aab66041f0f3","relation":"main_file","file_id":"22935","success":1,"file_name":"2026_LIPIcsESA_deBerg.pdf","date_updated":"2026-09-16T08:58:04Z","file_size":1102214,"date_created":"2026-09-16T08:58:04Z","access_level":"open_access","content_type":"application/pdf","creator":"dernst"}],"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"abstract":[{"text":"In the imprecise geometry model, the input is a family of regions F = (R₁, R₂, …,R_n), each containing a point p_i ∈ R_i. The task is then to compute some function of the points p₁,p₂,… p_n, in our case an implicit representation of their Pareto front. To this end, one may query a region R_i to retrieve its contained point p_i ∈ R_i. In this model, efficiency is interpreted in two ways: minimizing (i) the number of retrievals, and (ii) the computation time both for preprocessing, and the execution of the query stage, i.e. for computing which points to query and constructing the output. \r\nWe present an algorithm to construct (an implicit representation of) the Pareto front for possibly overlapping rectangles, that is instance-optimal with respect to the number of retrievals. This means that for every fixed input (F, P), there is no algorithm that retrieves asymptotically fewer regions to compute the output. This is a strong algorithmic quality, as it means that our algorithm is competitive even to clairvoyant algorithms which only have to verify the correctness of a correct guess. In terms of algorithmic running time, instance-optimality is provably unobtainable. We instead present an algorithm which is within a log n-factor of instance optimality. This generalizes earlier results which assumed the regions to not overlap, at only a minor cost in running time. \r\nFor unit squares, we present an algorithm that is not only instance optimal in the number of retrievals, but also universally optimal in terms of running time. This means that for any fixed set of regions F, no algorithm has a better worst-case running time for all possible point sets P. Thus, this work presents the first universally optimal algorithm for overlapping planar input. Compared to previous work, our result improves the degree to which the input regions may overlap, the preprocessing time, the number of retrievals, and the running time.","lang":"eng"}],"year":"2026","corr_author":"1","status":"public","title":"Instance optimal and universally optimal bounds for imprecise pareto fronts","OA_place":"publisher","acknowledgement":"This work was supported by the the VILLUM Foundation grant (VIL37507) \"Efficient Recomputations for Changeful Problems\".","supplementarymaterial":"no","conference":{"start_date":"2026-08-31","location":"L’Aquila, Italy","end_date":"2026-09-04","name":"ESA: European Symposium on Algorithms"}},{"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa_version":"Published Version","volume":388,"file_date_updated":"2026-09-16T09:20:49Z","ddc":["000"],"date_updated":"2026-09-16T09:21:35Z","date_created":"2026-09-13T22:01:52Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2026.101","project":[{"name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564"}],"intvolume":"       388","article_number":"101","author":[{"full_name":"Van Der Hoog, Ivor","last_name":"Van Der Hoog","first_name":"Ivor"},{"first_name":"Eva","last_name":"Rotenberg","full_name":"Rotenberg, Eva"},{"full_name":"Rutschmann, Daniel P","last_name":"Rutschmann","first_name":"Daniel P","id":"7397d908-b582-11f0-bf73-88b902e86527"}],"article_processing_charge":"Yes","OA_type":"gold","department":[{"_id":"MoHe"}],"scopus_import":"1","oa":1,"file":[{"access_level":"open_access","date_created":"2026-09-16T09:20:49Z","creator":"dernst","content_type":"application/pdf","file_size":892322,"date_updated":"2026-09-16T09:20:49Z","success":1,"file_id":"22937","file_name":"2026_LIPIcsESA_vanderHoog.pdf","relation":"main_file","checksum":"c552853bfa37e4b9a0f060107e464ed0"}],"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publication_status":"published","has_accepted_license":"1","quality_controlled":"1","das_tickbox":"0","publication":"34th Annual European Symposium on Algorithms","alternative_title":["LIPIcs"],"citation":{"ista":"Van Der Hoog I, Rotenberg E, Rutschmann DP. 2026. Tight Better-Than-Worst-Case bounds for element distinctness and set intersection. 34th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 101.","short":"I. Van Der Hoog, E. Rotenberg, D.P. Rutschmann, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","mla":"Van Der Hoog, Ivor, et al. “Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection.” <i>34th Annual European Symposium on Algorithms</i>, vol. 388, 101, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.101\">10.4230/LIPIcs.ESA.2026.101</a>.","chicago":"Van Der Hoog, Ivor, Eva Rotenberg, and Daniel P Rutschmann. “Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection.” In <i>34th Annual European Symposium on Algorithms</i>, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.101\">https://doi.org/10.4230/LIPIcs.ESA.2026.101</a>.","apa":"Van Der Hoog, I., Rotenberg, E., &#38; Rutschmann, D. P. (2026). Tight Better-Than-Worst-Case bounds for element distinctness and set intersection. In <i>34th Annual European Symposium on Algorithms</i> (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.101\">https://doi.org/10.4230/LIPIcs.ESA.2026.101</a>","ieee":"I. Van Der Hoog, E. Rotenberg, and D. P. Rutschmann, “Tight Better-Than-Worst-Case bounds for element distinctness and set intersection,” in <i>34th Annual European Symposium on Algorithms</i>, L’Aquila, Italy, 2026, vol. 388.","ama":"Van Der Hoog I, Rotenberg E, Rutschmann DP. Tight Better-Than-Worst-Case bounds for element distinctness and set intersection. In: <i>34th Annual European Symposium on Algorithms</i>. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.101\">10.4230/LIPIcs.ESA.2026.101</a>"},"day":"25","_id":"22915","supplementarymaterial":"yes","conference":{"start_date":"2026-08-31","location":"L’Aquila, Italy","name":"ESA: European Symposium on Algorithms","end_date":"2026-09-04"},"OA_place":"publisher","acknowledgement":"Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann thank the VILLUM Foundation\r\ngrant (VIL37507) “Efficient Recomputations for Changeful Problems” for supporting this work.\r\nDaniel Rutschmann is supported by the European Research Council (ERC) under the European\r\nUnion’s Horizon 2020 research and innovation programme (No. 101019564) ","corr_author":"1","status":"public","title":"Tight Better-Than-Worst-Case bounds for element distinctness and set intersection","year":"2026","abstract":[{"lang":"eng","text":"The element distinctness problem takes as input a list I of n values from a totally ordered universe, where pairwise comparisons between values are allowed, and the goal is to decide whether I contains any duplicates. It is a well-studied problem with a classical worst-case Ω(n log n) comparison-based lower bound by Fredman [TCS'76]. At first glance, this lower bound appears to rule out any algorithm more efficient than the naive approach of sorting I and comparing adjacent elements. However, upon closer inspection, the Ω(n log n) bound is overly pessimistic. For instance, if I contains n/2 identical elements, a median-finding algorithm will, regardless of the input order, find a duplicate in linear time. This raises a natural question: Are there comparison-based lower bounds for element distinctness that are sensitive to the amount of duplicates in the input instance?\r\nTo address this question, we derive instance-specific lower bounds. For any input instance I, we represent the combinatorial structure of the duplicates in I by an undirected graph G(I) that connects identical elements. Each such graph G is a union of cliques, and we study algorithms by their worst-case running time over all inputs I' with G(I') ≅ G. We establish an adversarial lower bound showing that, for any deterministic algorithm 𝒜, there exists a graph G and an algorithm 𝒜' that, for all inputs I with G(I) ≅ G, is a factor O(log log n) faster than 𝒜. Consequently, no deterministic algorithm can be o(log log n)-competitive for all graphs G. We complement this with an O(log log n)-competitive deterministic algorithm, thereby obtaining tight bounds for element distinctness that go beyond classical worst-case analysis. Subsequently, we study the related problem of set intersection. We show that no deterministic set intersection algorithm can be o(log n)-competitive, and provide an O(log n)-competitive deterministic algorithm. We find it interesting and surprising to discover tight O(log log n)-competitive bounds for element distinctness. Moreover, we find the separation between element distinctness and the set intersection problem unexpected."}],"month":"08","ec_funded":1,"type":"conference","researchdata_availability":"no","publication_identifier":{"isbn":["9783959774451"],"issn":["1868-8969"]},"keyword":["Comparison-based analysis","set intersection","universal optimality"],"external_id":{"arxiv":["2511.02954"]},"arxiv":1,"date_published":"2026-08-25T00:00:00Z","doi":"10.4230/LIPIcs.ESA.2026.101"}]