Search Results

Documents authored by Rysgaard, Casper Moldrup

Document
DOI: 10.4230/LIPIcs.MFCS.2025.87
Lazy B-Trees

Authors: Casper Moldrup Rysgaard and Sebastian Wild

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Lazy search trees (Sandlund & Wild FOCS 2020, Sandlund & Zhang SODA 2022) are sorted dictionaries whose update and query performance smoothly interpolates between that of efficient priority queues and binary search trees - automatically, depending on actual use; no adjustments are necessary to the data structure to realize the cost savings. In this paper, we design lazy B-trees, a variant of lazy search trees suitable for external memory that generalizes the speedup of B-trees over binary search trees wrt. input/output operations to the same smooth interpolation regime. A key technical difficulty to overcome is the lack of a (fully satisfactory) external variant of biased search trees, on which lazy search trees crucially rely. We give a construction for a subset of performance guarantees sufficient to realize external-memory lazy search trees, which we deem of independent interest. As one special case, lazy B-trees can be used as an external-memory priority queue, in which case they are competitive with some tailor-made heaps; indeed, they offer faster decrease-key and insert operations than known data structures.
Cite as

Casper Moldrup Rysgaard and Sebastian Wild. Lazy B-Trees. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 87:1-87:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{rysgaard_et_al:LIPIcs.MFCS.2025.87,
  author =	{Rysgaard, Casper Moldrup and Wild, Sebastian},
  title =	{{Lazy B-Trees}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{87:1--87:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.87},
  URN =		{urn:nbn:de:0030-drops-241949},
  doi =		{10.4230/LIPIcs.MFCS.2025.87},
  annote =	{Keywords: B-tree, lazy search trees, lazy updates, external memory, deferred data structures, database cracking}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.20
Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems

Authors: Ahmad Biniaz, Anil Maheshwari, Magnus Christian Ring Merrild, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, Eliot W. Robson, Casper Moldrup Rysgaard, Jens Kristian Refsgaard Schou, Thomas Shermer, Jack Spalding-Jamieson, Rolf Svenning, and Da Wei Zheng

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

Abstract
We introduce the contiguous art gallery problem which is to guard the boundary of a simple polygon with a minimum number of guards such that each guard covers exactly one contiguous portion of the boundary. Art gallery problems are often NP-hard. In particular, it is NP-hard to minimize the number of guards to see the boundary of a simple polygon, without the contiguity constraint. This paper is a merge of three concurrent works [Ahmad Biniaz et al., 2024; Magnus Christian Ring Merrild et al., 2024; Eliot W. Robson et al., 2024] each showing that (surprisingly) the contiguous art gallery problem is solvable in polynomial time. The common idea of all three approaches is developing a greedy function that maps a point on the boundary to the furthest point on the boundary so that the contiguous interval along the boundary between them could be guarded by one guard. Repeatedly applying this function immediately leads to an OPT+1 approximation. By studying this greedy algorithm, we present three different approaches that achieve an optimal solution. The first and second approach apply this greedy algorithm from different points on the boundary that could be found in advance or on the fly while traversing along the boundary (respectively). The third approach represents this function as a piecewise linear rational function, which can be reduced to an abstract arc cover problem involving infinite families of arcs. We identify other problems that can be represented by similar functions, and solve them via the third approach. From the combinatorial point of view, we show that any n-vertex polygon can be guarded by at most ⌊(n-2)/2⌋ guards. This bound is tight because there are polygons that require this many guards.
Cite as

Ahmad Biniaz, Anil Maheshwari, Magnus Christian Ring Merrild, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, Eliot W. Robson, Casper Moldrup Rysgaard, Jens Kristian Refsgaard Schou, Thomas Shermer, Jack Spalding-Jamieson, Rolf Svenning, and Da Wei Zheng. Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{biniaz_et_al:LIPIcs.SoCG.2025.20,
  author =	{Biniaz, Ahmad and Maheshwari, Anil and Merrild, Magnus Christian Ring and Mitchell, Joseph S. B. and Odak, Saeed and Polishchuk, Valentin and Robson, Eliot W. and Rysgaard, Casper Moldrup and Schou, Jens Kristian Refsgaard and Shermer, Thomas and Spalding-Jamieson, Jack and Svenning, Rolf and Zheng, Da Wei},
  title =	{{Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{20:1--20:21},
  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.20},
  URN =		{urn:nbn:de:0030-drops-231720},
  doi =		{10.4230/LIPIcs.SoCG.2025.20},
  annote =	{Keywords: Art Gallery Problem, Computational Geometry, Combinatorics, Discrete Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.35
On Finding Longest Palindromic Subsequences Using Longest Common Subsequences

Authors: Gerth Stølting Brodal, Rolf Fagerberg, and Casper Moldrup Rysgaard

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

Abstract
Two standard textbook problems illustrating dynamic programming are to find the longest common subsequence (LCS) between two strings and to find the longest palindromic subsequence (LPS) of a single string. A popular claim is that the longest palindromic subsequence in a string can be computed as the longest common subsequence between the string and the reversed string. We prove that the correctness of this claim depends on how the longest common subsequence is computed. In particular, we prove that the classical dynamic programming solution by Wagner and Fischer [JACM 1974] for finding an LCS in fact does find an LPS, while a slightly different LCS backtracking strategy makes the algorithm fail to always report a palindrome.
Cite as

Gerth Stølting Brodal, Rolf Fagerberg, and Casper Moldrup Rysgaard. On Finding Longest Palindromic Subsequences Using Longest Common Subsequences. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{brodal_et_al:LIPIcs.ESA.2024.35,
  author =	{Brodal, Gerth St{\o}lting and Fagerberg, Rolf and Rysgaard, Casper Moldrup},
  title =	{{On Finding Longest Palindromic Subsequences Using Longest Common Subsequences}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{35:1--35:16},
  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.35},
  URN =		{urn:nbn:de:0030-drops-211068},
  doi =		{10.4230/LIPIcs.ESA.2024.35},
  annote =	{Keywords: Palindromic subsequence, longest common subsequence, dynamic programming}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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