11 Search Results for "Dallant, Justin"

Document
DOI: 10.4230/LIPIcs.STACS.2026.68
Dynamic Pattern Matching with Wildcards

Authors: Arshia Ataee Naeini, Amir-Parsa Mobed, Masoud Seddighin, and Saeed Seddighin

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We study the fully dynamic pattern matching problem where the pattern may contain up to k wildcard symbols, each matching any symbol of the alphabet. Both the text and the pattern are subject to updates (insert, delete, change). We design an algorithm with 𝒪(n log² n) preprocessing and update/query time 𝒪̃(kn^{k/{k+1}} + k² log n). The bound is truly sublinear for a constant k, and sublinear when k = o(log n). We further complement our results with a conditional lower bound: assuming subquadratic preprocessing time, achieving truly sublinear update time for the case k = Ω(log n) would contradict the Strong Exponential Time Hypothesis (SETH). Finally, we develop sublinear algorithms for two special cases: - If the pattern contains w non-wildcard symbols, we give an algorithm with preprocessing time 𝒪(nw) and update time 𝒪(w + log n), which is truly sublinear whenever w is truly sublinear. - Using FFT technique combined with block decomposition, we design a deterministic truly sublinear algorithm with preprocessing time 𝒪(n^{1.8}) and update time 𝒪(n^{0.8} log n) for the case that there are at most two non-wildcards.
Cite as

Arshia Ataee Naeini, Amir-Parsa Mobed, Masoud Seddighin, and Saeed Seddighin. Dynamic Pattern Matching with Wildcards. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 68:1-68:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{naeini_et_al:LIPIcs.STACS.2026.68,
  author =	{Naeini, Arshia Ataee and Mobed, Amir-Parsa and Seddighin, Masoud and Seddighin, Saeed},
  title =	{{Dynamic Pattern Matching with Wildcards}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{68:1--68:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.68},
  URN =		{urn:nbn:de:0030-drops-255579},
  doi =		{10.4230/LIPIcs.STACS.2026.68},
  annote =	{Keywords: pattern matching, wildcards, dynamic algorithms, string algorithms, data structures}
}
Document
DOI: 10.4230/DagRep.15.5.1
Adaptive and Scalable Data Structures (Dagstuhl Seminar 25191)

Authors: Michael A. Bender, John Iacono, László Kozma, Eva Rotenberg, and Justin Dallant

Published in: Dagstuhl Reports, Volume 15, Issue 5 (2025)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 25191 "Adaptive and Scalable Data Structures". Data structures govern the organization and manipulation of data in computing systems across a broad range of applications. The efficiency and scalability of data structures has profound implications, motivating continued research on the entire spectrum from theoretical to practical. As the size and complexity of data sets increases and as the underlying computing infrastructure changes, data structures need to be continually redesigned with scalability in mind. Classical data structures also need reevaluation to better fit the requirements of modern applications. Adaptivity offers a way to design data structures that automatically take advantage of features of the underlying hardware, specific structure and biases in their usage, or side-information, and the limits of data structure adaptivity pose deep research questions. The goal of this seminar was to reflect on these complementary aspects of data structure research and to identify promising research questions. The program provides a snapshot of the current state of research and establishes possible future directions for the field.
Cite as

Michael A. Bender, John Iacono, László Kozma, Eva Rotenberg, and Justin Dallant. Adaptive and Scalable Data Structures (Dagstuhl Seminar 25191). In Dagstuhl Reports, Volume 15, Issue 5, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{bender_et_al:DagRep.15.5.1,
  author =	{Bender, Michael A. and Iacono, John and Kozma, L\'{a}szl\'{o} and Rotenberg, Eva and Dallant, Justin},
  title =	{{Adaptive and Scalable Data Structures (Dagstuhl Seminar 25191)}},
  pages =	{1--20},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2025},
  volume =	{15},
  number =	{5},
  editor =	{Bender, Michael A. and Iacono, John and Kozma, L\'{a}szl\'{o} and Rotenberg, Eva and Dallant, Justin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.15.5.1},
  URN =		{urn:nbn:de:0030-drops-252802},
  doi =		{10.4230/DagRep.15.5.1},
  annote =	{Keywords: Data structures, Algorithms, Big data, Computational models}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.23
The Price of Connectivity Augmentation on Planar Graphs

Authors: Hugo A. Akitaya, Justin Dallant, Erik D. Demaine, Michael Kaufmann, Linda Kleist, Frederick Stock, Csaba D. Tóth, and Torsten Ueckerdt

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
Given two classes of graphs, 𝒢₁ ⊆ 𝒢₂, and a c-connected graph G ∈ 𝒢₁, we wish to augment G with a smallest cardinality set of new edges F to obtain a k-connected graph G' = (V,E∪ F) ∈ 𝒢₂. In general, this is the c → k connectivity augmentation problem. Previous research considered variants where 𝒢₁ = 𝒢₂ is the class of planar graphs, plane graphs, or planar straight-line graphs. In all three settings, we prove that the c → k augmentation problem is NP-complete when 2 ≤ c < k ≤ 5. However, the connectivity of the augmented graph G' is at most 5 if 𝒢₂ is limited to planar graphs. We initiate the study of the c → k connectivity augmentation problem for arbitrary k ∈ ℕ, where 𝒢₁ is the class of planar graphs, plane graphs, or planar straight-line graphs, and 𝒢₂ is a beyond-planar class of graphs: 𝓁-planar, 𝓁-plane topological, or 𝓁-plane geometric graphs. We obtain tight bounds on the tradeoffs between the desired connectivity k and the local crossing number 𝓁 of the augmented graph G'. We also show that our hardness results apply to this setting. The connectivity augmentation problem for triangulations is intimately related to edge flips; and the minimum augmentation problem to the flip distance between triangulations. We prove that it is NP-complete to find the minimum flip distance between a given triangulation and a 4-connected triangulation, settling an open problem posed in 2014, and present an EPTAS for this problem.
Cite as

Hugo A. Akitaya, Justin Dallant, Erik D. Demaine, Michael Kaufmann, Linda Kleist, Frederick Stock, Csaba D. Tóth, and Torsten Ueckerdt. The Price of Connectivity Augmentation on Planar Graphs. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 23:1-23:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.GD.2025.23,
  author =	{A. Akitaya, Hugo and Dallant, Justin and Demaine, Erik D. and Kaufmann, Michael and Kleist, Linda and Stock, Frederick and T\'{o}th, Csaba D. and Ueckerdt, Torsten},
  title =	{{The Price of Connectivity Augmentation on Planar Graphs}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{23:1--23:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.23},
  URN =		{urn:nbn:de:0030-drops-250095},
  doi =		{10.4230/LIPIcs.GD.2025.23},
  annote =	{Keywords: connectivity augmentation, local crossing number, flip distance}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.16
Signotopes with Few Plus Signs

Authors: Helena Bergold, Lukas Egeling, and Hung P. Hoang

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Arrangements of pseudohyperplanes are widely studied in computational geometry. A rich subclass of pseudohyerplane arrangements, which has gained more attention in recent years, is the so-called signotopes. Introduced by Manin and Schechtman (1989), the higher Bruhat order is a natural order of r-signotopes on n elements, with the signotope corresponding to the cyclic arrangement as the minimal element. In this paper, we show that the lower (and by symmetry upper) levels of this higher Bruhat order contain the same number of elements for a fixed difference n-r. This result implies that given the difference d = n-r and p, the number of one-element extensions of the cyclic arrangement of n hyperplanes in ℝ^d with at most p points on one side of the extending pseudohyperplane does not depend on n, as long as n ≥ d + p.
Cite as

Helena Bergold, Lukas Egeling, and Hung P. Hoang. Signotopes with Few Plus Signs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bergold_et_al:LIPIcs.SoCG.2025.16,
  author =	{Bergold, Helena and Egeling, Lukas and Hoang, Hung P.},
  title =	{{Signotopes with Few Plus Signs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.16},
  URN =		{urn:nbn:de:0030-drops-231681},
  doi =		{10.4230/LIPIcs.SoCG.2025.16},
  annote =	{Keywords: flip graph, higher Bruhat order, signotope, counting, Ferrers diagram, one-element extension}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.44
An Optimal Randomized Algorithm for Finding the Saddlepoint

Authors: Justin Dallant, Frederik Haagensen, Riko Jacob, László Kozma, and Sebastian Wild

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
A saddlepoint of an n × n matrix is an entry that is the maximum of its row and the minimum of its column. Saddlepoints give the value of a two-player zero-sum game, corresponding to its pure-strategy Nash equilibria; efficiently finding a saddlepoint is thus a natural and fundamental algorithmic task. For finding a strict saddlepoint (an entry that is the strict maximum of its row and the strict minimum of its column) an O(n log* n)-time algorithm was recently obtained by Dallant, Haagensen, Jacob, Kozma, and Wild, improving the O(n log n) bounds from 1991 of Bienstock, Chung, Fredman, Schäffer, Shor, Suri and of Byrne and Vaserstein. In this paper we present an optimal O(n)-time algorithm for finding a strict saddlepoint based on random sampling. Our algorithm, like earlier approaches, accesses matrix entries only via unit-cost binary comparisons. For finding a (non-strict) saddlepoint, we extend an existing lower bound to randomized algorithms, showing that the trivial O(n²) runtime cannot be improved even with the use of randomness.
Cite as

Justin Dallant, Frederik Haagensen, Riko Jacob, László Kozma, and Sebastian Wild. An Optimal Randomized Algorithm for Finding the Saddlepoint. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 44:1-44:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dallant_et_al:LIPIcs.ESA.2024.44,
  author =	{Dallant, Justin and Haagensen, Frederik and Jacob, Riko and Kozma, L\'{a}szl\'{o} and Wild, Sebastian},
  title =	{{An Optimal Randomized Algorithm for Finding the Saddlepoint}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{44:1--44:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.44},
  URN =		{urn:nbn:de:0030-drops-211154},
  doi =		{10.4230/LIPIcs.ESA.2024.44},
  annote =	{Keywords: saddlepoint, matrix, comparison, search, randomized algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.43
An Improved Lower Bound on the Number of Pseudoline Arrangements

Authors: Fernando Cortés Kühnast, Justin Dallant, Stefan Felsner, and Manfred Scheucher

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
Arrangements of pseudolines are classic objects in discrete and computational geometry. They have been studied with increasing intensity since their introduction almost 100 years ago. The study of the number B_n of non-isomorphic simple arrangements of n pseudolines goes back to Goodman and Pollack, Knuth, and others. It is known that B_n is in the order of 2^Θ(n²) and finding asymptotic bounds on b_n = log₂(B_n)/n² remains a challenging task. In 2011, Felsner and Valtr showed that 0.1887 ≤ b_n ≤ 0.6571 for sufficiently large n. The upper bound remains untouched but in 2020 Dumitrescu and Mandal improved the lower bound constant to 0.2083. Their approach utilizes the known values of B_n for up to n = 12. We tackle the lower bound by utilizing dynamic programming and the Lindström–Gessel–Viennot lemma. Our new bound is b_n ≥ 0.2721 for sufficiently large n. The result is based on a delicate interplay of theoretical ideas and computer assistance.
Cite as

Fernando Cortés Kühnast, Justin Dallant, Stefan Felsner, and Manfred Scheucher. An Improved Lower Bound on the Number of Pseudoline Arrangements. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{corteskuhnast_et_al:LIPIcs.SoCG.2024.43,
  author =	{Cort\'{e}s K\"{u}hnast, Fernando and Dallant, Justin and Felsner, Stefan and Scheucher, Manfred},
  title =	{{An Improved Lower Bound on the Number of Pseudoline Arrangements}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{43:1--43:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.43},
  URN =		{urn:nbn:de:0030-drops-199880},
  doi =		{10.4230/LIPIcs.SoCG.2024.43},
  annote =	{Keywords: counting, pseudoline arrangement, recursive construction, bipermutation, divide and conquer, dynamic programming, computer-assisted proof}
}
Document
DOI: 10.4230/LIPIcs.FUN.2024.15
Polyamorous Scheduling

Authors: Leszek Gąsieniec, Benjamin Smith, and Sebastian Wild

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract
Finding schedules for pairwise meetings between the members of a complex social group without creating interpersonal conflict is challenging, especially when different relationships have different needs. We formally define and study the underlying optimisation problem: Polyamorous Scheduling. In Polyamorous Scheduling, we are given an edge-weighted graph and try to find a periodic schedule of matchings in this graph such that the maximal weighted waiting time between consecutive occurrences of the same edge is minimised. We show that the problem is NP-hard and that there is no efficient approximation algorithm with a better ratio than 4/3 unless P = NP. On the positive side, we obtain an O(log n)-approximation algorithm; indeed, an O(log Δ)-approximation for Δ the maximum degree, i.e., the largest number of relationships of any individual. We also define a generalisation of density from the Pinwheel Scheduling Problem, "poly density", and ask whether there exists a poly-density threshold similar to the 5/6-density threshold for Pinwheel Scheduling [Kawamura, STOC 2024]. Polyamorous Scheduling is a natural generalisation of Pinwheel Scheduling with respect to its optimisation variant, Bamboo Garden Trimming. Our work contributes the first nontrivial hardness-of-approximation reduction for any periodic scheduling problem, and opens up numerous avenues for further study of Polyamorous Scheduling.
Cite as

Leszek Gąsieniec, Benjamin Smith, and Sebastian Wild. Polyamorous Scheduling. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gasieniec_et_al:LIPIcs.FUN.2024.15,
  author =	{G\k{a}sieniec, Leszek and Smith, Benjamin and Wild, Sebastian},
  title =	{{Polyamorous Scheduling}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.15},
  URN =		{urn:nbn:de:0030-drops-199234},
  doi =		{10.4230/LIPIcs.FUN.2024.15},
  annote =	{Keywords: Periodic scheduling, Pinwheel scheduling, Edge-coloring, Chromatic index, Approximation algorithms, Hardness of approximation}
}
Document
DOI: 10.4230/DagRep.13.5.114
Scalable Data Structures (Dagstuhl Seminar 23211)

Authors: Gerth Stølting Brodal, John Iacono, László Kozma, Vijaya Ramachandran, and Justin Dallant

Published in: Dagstuhl Reports, Volume 13, Issue 5 (2023)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23211 "Scalable Data Structures". Data structures enable the organization, storage and retrieval of data across a variety of applications. As they are deployed at unprecedented scales, data structures can profoundly affect the efficiency of almost all computational tasks. The study of data structures thus continues to be an important and active area of research with an interplay between data structure design and analysis, developments in computer hardware, and the needs of modern applications. The extended abstracts included in this report give a snapshot of the current state of research on scalable data structures and establish directions for future developments in the field.
Cite as

Gerth Stølting Brodal, John Iacono, László Kozma, Vijaya Ramachandran, and Justin Dallant. Scalable Data Structures (Dagstuhl Seminar 23211). In Dagstuhl Reports, Volume 13, Issue 5, pp. 114-135, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{brodal_et_al:DagRep.13.5.114,
  author =	{Brodal, Gerth St{\o}lting and Iacono, John and Kozma, L\'{a}szl\'{o} and Ramachandran, Vijaya and Dallant, Justin},
  title =	{{Scalable Data Structures (Dagstuhl Seminar 23211)}},
  pages =	{114--135},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{5},
  editor =	{Brodal, Gerth St{\o}lting and Iacono, John and Kozma, L\'{a}szl\'{o} and Ramachandran, Vijaya and Dallant, Justin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.5.114},
  URN =		{urn:nbn:de:0030-drops-193676},
  doi =		{10.4230/DagRep.13.5.114},
  annote =	{Keywords: algorithms, big data, computational models, data structures, GPU computing, parallel computation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.39
Conditional Lower Bounds for Dynamic Geometric Measure Problems

Authors: Justin Dallant and John Iacono

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We give new polynomial lower bounds for a number of dynamic measure problems in computational geometry. These lower bounds hold in the Word-RAM model, conditioned on the hardness of either 3SUM, APSP, or the Online Matrix-Vector Multiplication problem [Henzinger et al., STOC 2015]. In particular we get lower bounds in the incremental and fully-dynamic settings for counting maximal or extremal points in ℝ³, different variants of Klee’s Measure Problem, problems related to finding the largest empty disk in a set of points, and querying the size of the i'th convex layer in a planar set of points. We also answer a question of Chan et al. [SODA 2022] by giving a conditional lower bound for dynamic approximate square set cover. While many conditional lower bounds for dynamic data structures have been proven since the seminal work of Pătraşcu [STOC 2010], few of them relate to computational geometry problems. This is the first paper focusing on this topic. Most problems we consider can be solved in O(nlog n) time in the static case and their dynamic versions have only been approached from the perspective of improving known upper bounds. One exception to this is Klee’s measure problem in ℝ², for which Chan [CGTA 2010] gave an unconditional Ω(√n) lower bound on the worst-case update time. By a similar approach, we show that such a lower bound also holds for an important special case of Klee’s measure problem in ℝ³ known as the Hypervolume Indicator problem, even for amortized runtime in the incremental setting.
Cite as

Justin Dallant and John Iacono. Conditional Lower Bounds for Dynamic Geometric Measure Problems. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dallant_et_al:LIPIcs.ESA.2022.39,
  author =	{Dallant, Justin and Iacono, John},
  title =	{{Conditional Lower Bounds for Dynamic Geometric Measure Problems}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{39:1--39:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.39},
  URN =		{urn:nbn:de:0030-drops-169777},
  doi =		{10.4230/LIPIcs.ESA.2022.39},
  annote =	{Keywords: Computational geometry, Fine-grained complexity, Dynamic data structures}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.13
How Fast Can We Play Tetris Greedily with Rectangular Pieces?

Authors: Justin Dallant and John Iacono

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
Consider a variant of Tetris played on a board of width w and infinite height, where the pieces are axis-aligned rectangles of arbitrary integer dimensions, the pieces can only be moved before letting them drop, and a row does not disappear once it is full. Suppose we want to follow a greedy strategy: let each rectangle fall where it will end up the lowest given the current state of the board. To do so, we want a data structure which can always suggest a greedy move. In other words, we want a data structure which maintains a set of O(n) rectangles, supports queries which return where to drop the rectangle, and updates which insert a rectangle dropped at a certain position and return the height of the highest point in the updated set of rectangles. We show via a reduction from the Multiphase problem [Pătraşcu, 2010] that on a board of width w = Θ(n), if the OMv conjecture [Henzinger et al., 2015] is true, then both operations cannot be supported in time O(n^{1/2-ε}) simultaneously. The reduction also implies polynomial bounds from the 3-SUM conjecture and the APSP conjecture. On the other hand, we show that there is a data structure supporting both operations in O(n^{1/2}log^{3/2}n) time on boards of width n^O(1), matching the lower bound up to an n^o(1) factor.
Cite as

Justin Dallant and John Iacono. How Fast Can We Play Tetris Greedily with Rectangular Pieces?. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dallant_et_al:LIPIcs.FUN.2022.13,
  author =	{Dallant, Justin and Iacono, John},
  title =	{{How Fast Can We Play Tetris Greedily with Rectangular Pieces?}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.13},
  URN =		{urn:nbn:de:0030-drops-159839},
  doi =		{10.4230/LIPIcs.FUN.2022.13},
  annote =	{Keywords: Tetris, Fine-grained complexity, Dynamic data structures, Axis-aligned rectangles}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.24
An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility

Authors: Jean Cardinal, Justin Dallant, and John Iacono

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
Afshani, Barbay and Chan (2017) introduced the notion of instance-optimal algorithm in the order-oblivious setting. An algorithm A is instance-optimal in the order-oblivious setting for a certain class of algorithms 𝒜 if the following hold: - A takes as input a sequence of objects from some domain; - for any instance σ and any algorithm A' ∈ 𝒜, the runtime of A on σ is at most a constant factor removed from the runtime of A' on the worst possible permutation of σ. If we identify permutations of a sequence as representing the same instance, this essentially states that A is optimal on every possible input (and not only in the worst case). We design instance-optimal algorithms for the problem of reporting, given a bichromatic set of points in the plane S, all pairs consisting of points of different color which span an empty axis-aligned rectangle (or reporting all points which appear in such a pair). This problem has applications for training-set reduction in nearest-neighbour classifiers. It is also related to the problem consisting of finding the decision boundaries of a euclidean nearest-neighbour classifier, for which Bremner et al. (2005) gave an optimal output-sensitive algorithm. By showing the existence of an instance-optimal algorithm in the order-oblivious setting for this problem we push the methods of Afshani et al. closer to their limits by adapting and extending them to a setting which exhibits highly non-local features. Previous problems for which instance-optimal algorithms were proven to exist were based solely on local relationships between points in a set.
Cite as

Jean Cardinal, Justin Dallant, and John Iacono. An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.ESA.2021.24,
  author =	{Cardinal, Jean and Dallant, Justin and Iacono, John},
  title =	{{An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.24},
  URN =		{urn:nbn:de:0030-drops-146057},
  doi =		{10.4230/LIPIcs.ESA.2021.24},
  annote =	{Keywords: computational geometry, instance-optimality, colored point sets, empty rectangles, visibility}
}
  • Refine by Type
  • 11 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 3 2025
  • 3 2024
  • 1 2023
  • 2 2022
  • Show More...

  • Refine by Author
  • 8 Dallant, Justin
  • 5 Iacono, John
  • 3 Kozma, László
  • 2 Wild, Sebastian
  • 1 A. Akitaya, Hugo
  • Show More...

  • Refine by Series/Journal
  • 9 LIPIcs
  • 2 DagRep

  • Refine by Classification
  • 6 Theory of computation → Computational geometry
  • 4 Theory of computation → Problems, reductions and completeness
  • 3 Theory of computation → Design and analysis of algorithms
  • 2 Mathematics of computing → Combinatorics
  • 2 Theory of computation → Data structures design and analysis
  • Show More...

  • Refine by Keyword
  • 2 Dynamic data structures
  • 2 Fine-grained complexity
  • 2 counting
  • 2 data structures
  • 1 Algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact