85 Search Results for "Munro, Ian"

Document
DOI: 10.4230/LIPIcs.SEA.2026.13
Practical Parallel Block Tree Construction

Authors: Robert Clausecker, Florian Kurpicz, and Etienne Palanga

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
The block tree [Belazzougui et al., J. Comput. Syst. Sci. '21] is a compressed representation of a length-n text that supports access, rank, and select queries while requiring only O(z log n/z) words of space, where z is the number of Lempel-Ziv factors of the text. In other words, its space requirements are asymptotically comparable to those of the compressed text itself. In practice, block trees offer query performance comparable to that of state-of-the-art compressed rank and select indices. However, their construction is significantly slower, and the fastest known construction algorithms additionally require a significant amount of working memory. To address these limitations, we propose fast and lightweight parallel algorithms for the efficient construction of block trees. Our algorithm achieves similar construction speed than the currently fastest block tree construction algorithm on a single core and is up to eight times faster using 64 cores, while requiring an order of magnitude less memory. Overall, we achieve a speedup of up to 15.5 on 64 cores, which is in line with the parallel construction of the Lempel-Ziv compression.
Cite as

Robert Clausecker, Florian Kurpicz, and Etienne Palanga. Practical Parallel Block Tree Construction. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{clausecker_et_al:LIPIcs.SEA.2026.13,
  author =	{Clausecker, Robert and Kurpicz, Florian and Palanga, Etienne},
  title =	{{Practical Parallel Block Tree Construction}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.13},
  URN =		{urn:nbn:de:0030-drops-260175},
  doi =		{10.4230/LIPIcs.SEA.2026.13},
  annote =	{Keywords: block tree, shared memory, compression, SIMD, Karp-Rabin fingerprints}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.10
Compressing Highly Repetitive Binary Trees with an Application to Range Minimum Queries

Authors: Gabriel Carmona and Filippo Lari

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Tree compression is a well-studied area that aims at reducing the size of tree representations by exploiting different forms of repetition. While the underlying theory is well understood, there is still significant room for experimental investigation, particularly in the design of compressed representations that efficiently support navigational queries. In this work, we address the problem of designing, engineering, and experimentally evaluating a compression technique for unlabeled binary trees based on repeated subtrees, yielding the minimal Directed Acyclic Graph (DAG) of the input tree. We show how this representation can be computed in linear time and space directly from a succinct encoding of the tree, and how it can be augmented with compact auxiliary data structures to support Lowest Common Ancestor (LCA) queries. When the input tree is the Cartesian tree of an array, LCA queries can be used to answer Range Minimum Queries (RMQs) on the underlying array. This is particularly relevant in the encoding model, where the array is not accessible at query time, and a space lower bound of 2n-O(log n) bits is known. Given the numerous applications of RMQs, we use this problem as a case study for our experimental evaluation, testing our implementation on 11 real-world datasets. Our experiments show that, on almost every dataset, our implementation is the most space-efficient, using as few as 0.11n bits, while still delivering practical query times.
Cite as

Gabriel Carmona and Filippo Lari. Compressing Highly Repetitive Binary Trees with an Application to Range Minimum Queries. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{carmona_et_al:LIPIcs.SEA.2026.10,
  author =	{Carmona, Gabriel and Lari, Filippo},
  title =	{{Compressing Highly Repetitive Binary Trees with an Application to Range Minimum Queries}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.10},
  URN =		{urn:nbn:de:0030-drops-260140},
  doi =		{10.4230/LIPIcs.SEA.2026.10},
  annote =	{Keywords: tree compression, range minimum query, compact data structures, algorithm engineering, experimental evaluation}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.11
Wavelet Forests Revisited

Authors: Eric Chiu and Dominik Kempa

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Rank and select queries are basic operations on sequences, with applications in compressed text indexes and other space-efficient data structures. One of the standard data structures supporting these queries is the wavelet tree. In this paper, we study wavelet forests, that is, wavelet-tree structures based on the fixed-block compression boosting technique. Such structures partition the input sequence into fixed-size blocks and build a separate wavelet tree for each block. Previous work showed that this approach yields strong practical performance for rank queries. We extend wavelet forests to support select queries. We show that select support can be added with little additional space overhead and that the resulting structures remain practically efficient. In experiments on a range of non-repetitive and repetitive inputs, wavelet forests are competitive with, and in most cases outperform, standalone wavelet-tree implementations. We also study the effect of internal parameters, including superblock size and navigational data, on select-query performance.
Cite as

Eric Chiu and Dominik Kempa. Wavelet Forests Revisited. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 11:1-11:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chiu_et_al:LIPIcs.SEA.2026.11,
  author =	{Chiu, Eric and Kempa, Dominik},
  title =	{{Wavelet Forests Revisited}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{11:1--11:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.11},
  URN =		{urn:nbn:de:0030-drops-260152},
  doi =		{10.4230/LIPIcs.SEA.2026.11},
  annote =	{Keywords: wavelet tree, wavelet forest, select queries}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.12
Fast Select Queries Using Hybrid Bitvectors

Authors: Eric Chiu and Dominik Kempa

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
One of the central problems in the design of compressed data structures is the efficient support for rank and select queries on bitvectors. These two operations form the backbone of more complex data structures used for the compact representation of texts, trees, graphs, or grids. One effective solution is the so-called hybrid bitvector implementation, which partitions the input bitvector into blocks and adaptively selects an encoding method - such as run-length, plain, or minority encoding - based on local redundancy. Experiments have shown that hybrid bitvectors achieve excellent all-around performance on repetitive and non-repetitive inputs. Current hybrid bitvector implementations, however, support only rank queries (i.e., counting the number of ones up to a given position) and lack support for select queries (which ask for the position of a given occurrence of a given bit), which limits their applicability. In this paper, we propose a method to add support for select queries to hybrid bitvectors, and we evaluate the resulting implementation on repetitive and non-repetitive inputs. Our results show that hybrid bitvectors offer very strong all-around performance, combining high query speed with space efficiency and remaining consistently on or near the Pareto frontier.
Cite as

Eric Chiu and Dominik Kempa. Fast Select Queries Using Hybrid Bitvectors. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 12:1-12:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chiu_et_al:LIPIcs.SEA.2026.12,
  author =	{Chiu, Eric and Kempa, Dominik},
  title =	{{Fast Select Queries Using Hybrid Bitvectors}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{12:1--12:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.12},
  URN =		{urn:nbn:de:0030-drops-260168},
  doi =		{10.4230/LIPIcs.SEA.2026.12},
  annote =	{Keywords: compressed bitvectors, hybrid bitvector, select queries}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.2
Near-Real-Time Solutions for Online String Problems

Authors: Dominik Köppl and Gregory Kucherov

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
Based on the Breslauer-Italiano online suffix tree construction algorithm (2013) with double logarithmic worst-case guarantees on the update time per letter, we develop near-real-time algorithms for several classical problems on strings, including the computation of the longest repeating suffix array, the (reversed) Lempel-Ziv 77 factorization, and the maintenance of minimal unique substrings, all in an online manner. Our solutions improve over the best known running times for these problems in terms of the worst-case time per letter, for which we achieve a poly-log-logarithmic time complexity, within a linear space. Best known results for these problems require a poly-logarithmic time complexity per letter or only provide amortized complexity bounds. As a result of independent interest, we give conversions between the longest previous factor array and the longest repeating suffix array in space and time bounds based on their irreducible representations, which can have sizes sublinear in the length of the input string.
Cite as

Dominik Köppl and Gregory Kucherov. Near-Real-Time Solutions for Online String Problems. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{koppl_et_al:LIPIcs.CPM.2026.2,
  author =	{K\"{o}ppl, Dominik and Kucherov, Gregory},
  title =	{{Near-Real-Time Solutions for Online String Problems}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{2:1--2:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.2},
  URN =		{urn:nbn:de:0030-drops-259287},
  doi =		{10.4230/LIPIcs.CPM.2026.2},
  annote =	{Keywords: online algorithms, string algorithms, suffix tree, real-time computation, Lempel-Ziv factorization, minimal unique substrings}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.9
Indexing and Encoding Arrays for Element Distinctness Queries

Authors: Johannes Fischer and Filippo Lari

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
We introduce the data structure variant of the well-known element distinctness problem. Given an array of n elements, the goal is to preprocess the array into a data structure that supports queries asking whether all elements within a given query range are distinct. This has applications in text indexing and possibly also in other algorithmic domains. In the indexing model (where access to the input array is allowed), we design a data structure using O((n log b)/b) bits and answering queries in the time needed to solve an online element distinctness instance of size O(b), for any b ≥ 1. As a concrete instantiation of this, there exists an index that answers queries in O(log log log n) time using O({n log²(log log log n)}/{log log log n}) bits of additional space. Moving to the encoding model (where access to the input array is not allowed), we begin by proving an information-theoretic lower bound for the space usage of 2n-O(log n) bits, and then design a matching encoding with O(1) time queries. We then consider the case in which the alphabet size σ is constant. In this setting, the lower bound can be refined to n log(r_σ) - 3 log(σ+2) + O(1) bits, where r_σ = 4cos²(π/(σ+2)). This lower bound is matched by an encoding with O(1) time queries.
Cite as

Johannes Fischer and Filippo Lari. Indexing and Encoding Arrays for Element Distinctness Queries. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.CPM.2026.9,
  author =	{Fischer, Johannes and Lari, Filippo},
  title =	{{Indexing and Encoding Arrays for Element Distinctness Queries}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.9},
  URN =		{urn:nbn:de:0030-drops-259350},
  doi =		{10.4230/LIPIcs.CPM.2026.9},
  annote =	{Keywords: element distinctness, range queries, lower bounds, succinct data structures}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.11
Matching Regular-Typed Pattern Languages: Quadratic-Time Algorithms

Authors: Yuya Uezato

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
Pattern languages (PAT) are a class of languages generated by expressions called patterns that may contain variables. In a pattern, each variable can be instantiated with an arbitrary string. Typed pattern languages extend PAT by associating a type (constraint) with each variable that restricts the domain of allowed substitutions. In this paper, we study regular-typed PAT (PATwRT), where all types are represented either by a regular expression or by an ε-NFA. We consider the PATwRT matching problem for patterns with a single repeated variable of the form P = α₁ β α₂ β ⋯ β α_K. We present simple algorithms whose running time is linear in K and quadratic in the input length N, with polynomial dependence on the sizes of the type representations. Our results extend previous quadratic-time work in two directions: (1) the quadratic-time algorithm for untyped PAT of Fernau et al. (STACS 2015), and (2) the quadratic-time algorithm for the restricted PATwRT K = 3, i.e., α₁ β α₂ β α₃ of Nogami and Terauchi (MFCS 2025).
Cite as

Yuya Uezato. Matching Regular-Typed Pattern Languages: Quadratic-Time Algorithms. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{uezato:LIPIcs.CPM.2026.11,
  author =	{Uezato, Yuya},
  title =	{{Matching Regular-Typed Pattern Languages: Quadratic-Time Algorithms}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.11},
  URN =		{urn:nbn:de:0030-drops-259374},
  doi =		{10.4230/LIPIcs.CPM.2026.11},
  annote =	{Keywords: Pattern languages, Regular expressions, String algorithms}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.13
Faster Algorithms for Shortest Unique or Absent Substrings

Authors: Panagiotis Charalampopoulos, Manal Mohamed, Solon P. Pissis, Hilde Verbeek, and Wiktor Zuba

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
We revisit two well-known algorithmic problems on strings: computing a shortest unique substring (SUS) and a shortest absent substring (SAS) in a string S of length n. Both problems admit folklore 𝒪(n)-time solutions using the suffix tree of S. However, for small alphabets, this complexity is not necessarily optimal in the word RAM model, where a string of length n over alphabet [0,σ) can be stored in 𝒪(n log σ/log n) space and read in 𝒪(n log σ/log n) time. We present an 𝒪(n log σ/√{log n})-time algorithm for computing a SUS in S. This algorithm decomposes the problem according to the length and the period of the sought substring and uses several tools and techniques, such as synchronizing sets, the analysis of runs, and wavelet trees, to reduce the computation of a SUS to a simple geometric problem. Further, we adapt this algorithm and combine it with an efficient construction of de Bruijn sequences in order to obtain an 𝒪(n log σ/√{log n})-time algorithm for computing a SAS in S.
Cite as

Panagiotis Charalampopoulos, Manal Mohamed, Solon P. Pissis, Hilde Verbeek, and Wiktor Zuba. Faster Algorithms for Shortest Unique or Absent Substrings. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{charalampopoulos_et_al:LIPIcs.SWAT.2026.13,
  author =	{Charalampopoulos, Panagiotis and Mohamed, Manal and Pissis, Solon P. and Verbeek, Hilde and Zuba, Wiktor},
  title =	{{Faster Algorithms for Shortest Unique or Absent Substrings}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.13},
  URN =		{urn:nbn:de:0030-drops-260493},
  doi =		{10.4230/LIPIcs.SWAT.2026.13},
  annote =	{Keywords: string algorithms, unique substrings, absent substrings, absent words}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.25
Compressed Index with Construction in Compressed Space

Authors: Dmitry Kosolobov

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
Suppose that we are given a string s of length n over an alphabet {0,1,…,n^O(1)} and δ is the string complexity of s, a known compression measure. We describe an index on s with O(δlog(n/δ)) space, measured in O(log n)-bit machine words, which can search in s any string of length m in O(m + (occ + 1)log^ε n) time, where occ is the number of occurrences and ε > 0 is any fixed constant (the big-O in the space bound hides factor 1/ε). Crucially, the index can be built in O(n log n) expected time by one left-to-right pass on the string s in a streaming fashion with O(δlog(n/δ)) construction space. The index does not use the Karp-Rabin fingerprints, and the randomization in the construction time can be eliminated by using deterministic dictionaries instead of hash tables (with a slowdown). The search time matches currently best results and the space is almost optimal (the known optimum is O(δlog n/(δα)), where α = log_σ n and σ is the alphabet size, and it coincides with O(δlog(n/δ)) when δ = O(n/α²)). This is the first index that can be constructed within such space and with such time guarantees. To avoid uninteresting marginal cases, all above bounds are stated for δ ≥ Ω(log log n).
Cite as

Dmitry Kosolobov. Compressed Index with Construction in Compressed Space. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 25:1-25:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kosolobov:LIPIcs.CPM.2026.25,
  author =	{Kosolobov, Dmitry},
  title =	{{Compressed Index with Construction in Compressed Space}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{25:1--25:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.25},
  URN =		{urn:nbn:de:0030-drops-259515},
  doi =		{10.4230/LIPIcs.CPM.2026.25},
  annote =	{Keywords: compressed index, pattern matching, string complexity, grammar, block tree}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.27
New Results on Three-Sided Skyline Range Counting and Reporting

Authors: Suruchi Kushwaha and Yakov Nekrich

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
In the orthogonal skyline range counting (resp. reporting) problem we store the set of points P in a data structure so that for any query range Q the number of points (resp. the list of all points) on the skyline of Q∩ P can be found efficiently. In this paper we study two-dimensional range counting and reporting problems in the case when the query range is bounded on three sides. We describe a linear-space data structure that answers top-open three-sided skyline counting queries in O(log log N) time, where N is the number of points stored in the data structure. We also show that bottom-open three-sided skyline counting queries are as difficult as general four-sided queries and any data structure that uses O(Nlog^c N) space for a constant c requires Ω(log N/log log N) time to answer such queries. Next, we turn to skyline color range queries. In this variant of the problem each point in P is assigned a color and we must count (resp. report) the distinct colors of point on the skyline of Q∩ P. We describe an O(N)-space data structure that answers top-open three-sided color counting queries in O(log N/log log N) time. Finally, we study top-open three-sided skyline color reporting in the EM model and describe a data structure that uses linear space and answers queries in O(k/B+1) I/Os where k is the number of colors on the skyline. This is the first external-memory data structure with optimal query cost and space usage for this problem.
Cite as

Suruchi Kushwaha and Yakov Nekrich. New Results on Three-Sided Skyline Range Counting and Reporting. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kushwaha_et_al:LIPIcs.SWAT.2026.27,
  author =	{Kushwaha, Suruchi and Nekrich, Yakov},
  title =	{{New Results on Three-Sided Skyline Range Counting and Reporting}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.27},
  URN =		{urn:nbn:de:0030-drops-260631},
  doi =		{10.4230/LIPIcs.SWAT.2026.27},
  annote =	{Keywords: Data Structures, Range Searching, Skyline Queries}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.36
Upward Book Embeddings of Partitioned Digraphs

Authors: Giordano Da Lozzo, Fabrizio Frati, and Ignaz Rutter

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
In 1999, Heath, Pemmaraju, and Trenk [SIAM J. Comput. 28(4), 1999] extended the classic notion of book embeddings to digraphs, introducing the concept of upward book embeddings, in which the vertices must appear along the spine in a topological order and the edges are partitioned into pages, so that no two edges in the same page cross. For a partitioned digraph G = (V, ⋃^k_{i=1} E_i), that is, a digraph whose edge set is partitioned into k subsets, an upward book embedding is required to assign edges to pages as prescribed by the given partition. In a companion paper, Heath and Pemmaraju [SIAM J. Comput. 28(5), 1999] proved that the problem of testing the existence of an upward book embedding of a partitioned digraph is linear-time solvable for k = 1 and recently Akitaya, Demaine, Hesterberg, and Liu [GD, 2017] have shown the problem NP-complete for k ≥ 3. In this paper, we study upward book embeddings of partitioned digraphs and focus on the unsolved case k = 2. Our first main result is a novel characterization of the upward embeddings that support an upward book embedding in two pages. We exploit this characterization in several ways, and obtain a rich picture of the complexity landscape of the problem. First, we show that the problem remains NP-complete when k = 2, thus closing the complexity gap for the problem. Second, we show that, for an n-vertex partitioned digraph with a prescribed planar embedding, the existence of an upward book embedding that respects the given planar embedding can be tested in O(n log³ n) time. Finally, leveraging the SPQ(R)-tree decomposition of biconnected graphs into triconnected components, we present a cubic-time testing algorithm for biconnected directed partial 2-trees.
Cite as

Giordano Da Lozzo, Fabrizio Frati, and Ignaz Rutter. Upward Book Embeddings of Partitioned Digraphs. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dalozzo_et_al:LIPIcs.SoCG.2026.36,
  author =	{Da Lozzo, Giordano and Frati, Fabrizio and Rutter, Ignaz},
  title =	{{Upward Book Embeddings of Partitioned Digraphs}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{36:1--36:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.36},
  URN =		{urn:nbn:de:0030-drops-258424},
  doi =		{10.4230/LIPIcs.SoCG.2026.36},
  annote =	{Keywords: upward book embeddings, partitioned digraphs, SPQ-trees, 2-trees}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.45
Line Segment Visibility in Simple Polygons: Exact, Robust, Scalable Computation and Applications

Authors: Sándor P. Fekete, Prahlad Narasimhan Kasthurirangan, Phillip Keldenich, Fabian Kollhoff, Chek-Manh Loi, and Michael Perk

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
The weak visibility polygon of a line segment s inside a simple polygon P, denoted by V_P(s), is the region of the polygon that is visible from at least one point on s. Given its fundamental nature in computational geometry, several algorithms have been proposed to compute weak visibility polygons efficiently, each with different trade-offs in terms of preprocessing time, query time, and space complexity. Although there are many applications that require computing these polygons such as computer graphics, robot motion planning, and network communication systems, there is a lack of any implementations of these algorithms in the literature - not to mention one that is exact, robust, and scalable. Furthermore, weak segment visibility polygons are used as basic building blocks in several other algorithms, such as in minimum-link path computation. In this work, we present an implementation of an optimal linear-time algorithm for computing the weak visibility polygon of a segment inside a triangulated simple polygon. Our implementation provides exact, robust geometric primitives and optimizations to handle large inputs with more than 18,000,000 vertices. We demonstrate two concrete applications: (1) construction of window partitions, a standard data structure in visibility algorithms, and (2) support for optimal minimum-link path queries between two points in a simple polygon, the latter serving as a direct use case of the former. Experimental results on a variety of polygon families confirm that the end-to-end running time scales linearly with the size of the polygon and is dominated by the cost of computing the triangulation, validating the practicality and scalability of the approach. The implementation is released as open source in the format of a CGAL package to support reproducibility and further research.
Cite as

Sándor P. Fekete, Prahlad Narasimhan Kasthurirangan, Phillip Keldenich, Fabian Kollhoff, Chek-Manh Loi, and Michael Perk. Line Segment Visibility in Simple Polygons: Exact, Robust, Scalable Computation and Applications. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2026.45,
  author =	{Fekete, S\'{a}ndor P. and Kasthurirangan, Prahlad Narasimhan and Keldenich, Phillip and Kollhoff, Fabian and Loi, Chek-Manh and Perk, Michael},
  title =	{{Line Segment Visibility in Simple Polygons: Exact, Robust, Scalable Computation and Applications}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{45:1--45:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.45},
  URN =		{urn:nbn:de:0030-drops-258516},
  doi =		{10.4230/LIPIcs.SoCG.2026.45},
  annote =	{Keywords: Visibility, line segments, link distance, window partition, computation, implementation, robustness, scalability, exactness, CGAL}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2026.98
Interactive Uniform Floodlight Illumination and Rotating Rays Voronoi Diagrams (Media Exposition)

Authors: Carlos Alegría, Ioannis Mantas, Marko Savić, and Martin Suderland

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Floodlight illumination problems are art-gallery variants, where a target domain needs to be illuminated by guards, each associated with a field of view. The rotating rays Voronoi diagram is a Voronoi diagram with rays as sites under the angular distance. There is a natural connection of this Voronoi structure with the problem of finding the minimum aperture such that a given set of uniform aperture floodlights illuminates a target domain. In this work we present an interactive visualization software for such problems, supporting different angular distances, namely, oriented and unoriented versions, and for different domains, namely, the plane and simple polygons.
Cite as

Carlos Alegría, Ioannis Mantas, Marko Savić, and Martin Suderland. Interactive Uniform Floodlight Illumination and Rotating Rays Voronoi Diagrams (Media Exposition). In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 98:1-98:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alegria_et_al:LIPIcs.SoCG.2026.98,
  author =	{Alegr{\'\i}a, Carlos and Mantas, Ioannis and Savi\'{c}, Marko and Suderland, Martin},
  title =	{{Interactive Uniform Floodlight Illumination and Rotating Rays Voronoi Diagrams}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{98:1--98:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.98},
  URN =		{urn:nbn:de:0030-drops-259048},
  doi =		{10.4230/LIPIcs.SoCG.2026.98},
  annote =	{Keywords: rotating rays Voronoi diagram, oriented angular distance, unoriented angular distance, Brocard angle, floodlight illumination, coverage problems, visualization software}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.17
Sorting Magazines and Boxes

Authors: Gabriele Fici, Manal Mohamed, and Jakub Radoszewski

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
It is a rainy Sunday. Agata has decided to sort the magazines on her shelf. Because the magazines are quite thin, she refuses to insert one between two others, preferring to move them only to the ends of the shelf. She has conceived a strategy for this but is unsure of its efficiency. Meanwhile, in the adjacent room, her three-year-old son, Szymon, has just finished his Montessori tower puzzle and is figuring out how to put it away. He has adopted a very intuitive approach to nesting the boxes, though he is not certain it will ultimately succeed. Agata and Szymon are employing very primitive strategies. While many sorting algorithms are remarkably simple to explain and implement-specifically, the class of in-place sorting algorithms with 𝒪(n²) worst-case and average-case running time and constant space requirements (e.g., Bubble Sort, Gnome Sort)-the strategies discussed here offer a unique perspective on "intuitive" sorting. Our contribution aims to enrich the field of simple sorting algorithms. Interestingly, determining the exact worst-case complexity of some of the proposed algorithms remains an open problem.
Cite as

Gabriele Fici, Manal Mohamed, and Jakub Radoszewski. Sorting Magazines and Boxes. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fici_et_al:LIPIcs.FUN.2026.17,
  author =	{Fici, Gabriele and Mohamed, Manal and Radoszewski, Jakub},
  title =	{{Sorting Magazines and Boxes}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.17},
  URN =		{urn:nbn:de:0030-drops-257368},
  doi =		{10.4230/LIPIcs.FUN.2026.17},
  annote =	{Keywords: Sorting algorithm, analysis of algorithms, intuitive sorting}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.62
Relative Compressed Reverse Suffix Array

Authors: Muhammed Oguzhan Kulekci, Mano Prakash Parthasarathi, Rahul Shah, and Sharma V. Thankachan

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

Abstract
Suffix trees and suffix arrays are two fundamental data structures in the field of string algorithms. For a string (a.k.a. text or sequence) of length n over an alphabet of size σ, these structures typically require O(nlog n) bits of space. The FM-index provides a compressed representation of the suffix array in ≈ nlog σ bits, allowing for efficient queries on both the suffix array and its inverse array in near logarithmic time. In certain applications, such as approximate pattern matching (i.e., with wildcards, mismatches, edits), there is a need to access the suffix array of a text, as well as the suffix array of text’s reverse. Motivated by this, we explore the possibility of encoding the suffix array of the reversed text in a compact form, assuming the availability of the FM-index for the original text. Our first solution is an O(n)-bit (relative) encoding of the suffix array of the reversed text, with the time for decoding an entry being only O(log^*n) times that of decoding an entry in the text’s suffix array using FM-index. We then demonstrate how to reduce the space to O(n/κ) bits for a parameter κ, while multiplicative factor in time becomes approximately O(κlog^*n+κ³). We can also support inverse suffix array and longest common extension queries on the reversed text. These results are achieved through some careful and non-trivial application of various succinct data structure techniques.
Cite as

Muhammed Oguzhan Kulekci, Mano Prakash Parthasarathi, Rahul Shah, and Sharma V. Thankachan. Relative Compressed Reverse Suffix Array. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 62:1-62:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kulekci_et_al:LIPIcs.STACS.2026.62,
  author =	{Kulekci, Muhammed Oguzhan and Parthasarathi, Mano Prakash and Shah, Rahul and Thankachan, Sharma V.},
  title =	{{Relative Compressed Reverse Suffix Array}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{62:1--62:21},
  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.62},
  URN =		{urn:nbn:de:0030-drops-255512},
  doi =		{10.4230/LIPIcs.STACS.2026.62},
  annote =	{Keywords: String Matching, Text Indexing, Data Structures, Suffix Trees}
}
  • Refine by Type
  • 85 Document/PDF
  • 61 Document/HTML

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

  • Refine by Author
  • 20 Munro, J. Ian
  • 10 Nekrich, Yakov
  • 6 He, Meng
  • 5 El-Zein, Hicham
  • 5 Wu, Kaiyu
  • Show More...

  • Refine by Series/Journal
  • 72 LIPIcs
  • 9 OASIcs
  • 1 TGDK
  • 3 DagSemRep

  • Refine by Classification
  • 26 Theory of computation → Data structures design and analysis
  • 14 Theory of computation → Data compression
  • 13 Theory of computation → Design and analysis of algorithms
  • 11 Theory of computation → Pattern matching
  • 5 Information systems → Information retrieval
  • Show More...

  • Refine by Keyword
  • 6 Data Structures
  • 6 data structures
  • 6 succinct data structures
  • 4 Burrows-Wheeler Transform
  • 4 string 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