Schloss Dagstuhl – Leibniz Center for Informatics
DROPS Dagstuhl Research Online Publication ServerNot a member yet
23028 research outputs found
Sort by
On Palindromic Periodicities
Get PDFWe say a finite word x is a palindromic periodicity if there exist two palindromes p and s such that |x| ≥ |ps| and x is a prefix of the infinite periodic word (ps)^ω = pspsps⋯. In this paper we examine the palindromic periodicities occurring in some classical infinite words, such as Sturmian words, episturmian words, the Thue-Morse word, the period-doubling word, the Rudin-Shapiro word, the paperfolding word, and the Tribonacci word, and prove a number of results about them. We also prove results about words with the smallest number of distinct palindromic periodicities
Net Occurrences in Fibonacci and Thue-Morse Words
Get PDFA net occurrence of a repeated string in a text is an occurrence with unique left and right extensions, and the net frequency of the string is the number of its net occurrences in the text. Originally introduced for applications in Natural Language Processing, net frequency has recently gained attention for its algorithmic aspects. Guo et al. [CPM 2024] and Ohlebusch et al. [SPIRE 2024] focus on its computation in the offline setting, while Guo et al. [SPIRE 2024], Inenaga [arXiv 2024], and Mieno and Inenaga [CPM 2025] tackle the online counterpart. Mieno and Inenaga also characterize net occurrences in terms of the minimal unique substrings of the text. Additionally, Guo et al. [CPM 2024] initiate the study of net occurrences in Fibonacci words to establish a lower bound on the asymptotic running time of algorithms. Although there has been notable progress in algorithmic developments and some initial combinatorial insights, the combinatorial aspects of net occurrences have yet to be thoroughly examined. In this work, we make two key contributions. First, we confirm the conjecture that each Fibonacci word contains exactly three net occurrences. Second, we show that each Thue-Morse word contains exactly nine net occurrences. To achieve these results, we introduce the notion of overlapping net occurrence cover, which narrows down the candidate net occurrences in any text. Furthermore, we provide a precise characterization of occurrences of Fibonacci and Thue-Morse words of smaller order, offering structural insights that may have independent interest and potential applications in algorithm analysis and combinatorial properties of these words
Space-Efficient Online Computation of String Net Occurrences
Get PDFA substring u of a string T is said to be a repeat if u occurs at least twice in T. An occurrence [i..j] of a repeat u in T is said to be a net occurrence if each of the substrings aub = T[i-1..j+1], au = T[i-1..j], and ub = T[i..j+1] occurs exactly once in T. The occurrence [i-1..j+1] of aub is said to be an extended net occurrence of u. Let T be an input string of length n over an alphabet of size σ, and let ENO(T) denote the set of extended net occurrences of repeats in T. Guo et al. [SPIRE 2024] presented an online algorithm which can report ENO(T[1..i]) in T[1..i] in O(nσ²) time, for each prefix T[1..i] of T. Very recently, Inenaga [arXiv 2024] gave a faster online algorithm that can report ENO(T[1..i]) in optimal O(#ENO(T[1..i])) time for each prefix T[1..i] of T, where #S denotes the cardinality of a set S. Both of the aforementioned data structures can be maintained in O(n log σ) time and occupy O(n) space, where the O(n)-space requirement comes from the suffix tree data structure. In particular, Inenaga’s recent algorithm is based on Weiner’s right-to-left online suffix tree construction. In this paper, we show that one can modify Ukkonen’s left-to-right online suffix tree construction algorithm in O(n) space, so that ENO(T[1..i]) can be reported in optimal O(#ENO(T[1..i])) time for each prefix T[1..i] of T. This is an improvement over Guo et al.’s method that is also based on Ukkonen’s algorithm. Further, this leads us to the two following space-efficient alternatives:
- A sliding-window algorithm of O(d) working space that can report ENO(T[i-d+1..i]) in optimal O(#ENO(T[i-d+1..i])) time for each sliding window T[i-d+1..i] of size d in T.
- A CDAWG-based online algorithm of O() working space that can report ENO(T[1..i]) in optimal O(#ENO(T[1..i])) time for each prefix T[1..i] of T, where < 2n is the number of edges in the CDAWG for T. All of our proposed data structures can be maintained in O(n log σ) time for the input online string T. We also discuss that the extended net occurrences of repeats in T can be fully characterized in terms of the minimal unique substrings (MUSs) in T
Extremal Betti Numbers and Persistence in Flag Complexes
Get PDFWe investigate several problems concerning extremal Betti numbers and persistence in filtrations of flag complexes. For graphs on n vertices, we show that β_k(X(G)) is maximal when G = _{n,k+1}, the Turán graph on k+1 partition classes, where X(G) denotes the flag complex of G. Building on this, we construct an edgewise (one edge at a time) filtration = G₁ ⊆ ⋯ ⊆ _{n,k+1} for which β_k(X(G_i)) is maximal for all graphs on n vertices and i edges. Moreover, the persistence barcode ℬ_k(X(G)) achieves a maximal number of intervals, and total persistence, among all edgewise filtrations with |E(_{n,k+1})| edges.
For k = 1, we consider edgewise filtrations of the complete graph K_n. We show that the maximal number of intervals in the persistence barcode is obtained precisely when G_{⌈n/2⌉ ⋅ ⌊n/2⌋} = _{n,2}. Among such filtrations, we characterize those achieving maximal total persistence. We further show that no filtration can optimize β₁(X(G_i)) for all i, and conjecture that our filtrations maximize the total persistence over all edgewise filtrations of K_n
Simplification of Trajectory Streams
Get PDFWhile there are software systems that simplify trajectory streams on the fly, few curve simplification algorithms with quality guarantees fit the streaming requirements. We present streaming algorithms for two such problems under the Fréchet distance d_F in ℝ^d for some constant d ≥ 2.
Consider a polygonal curve τ in ℝ^d in a stream. We present a streaming algorithm that, for any ε ∈ (0,1) and δ > 0, produces a curve σ such that d_F(σ,τ[v₁,v_i]) ≤ (1+ε)δ and |σ| ≤ 2 opt-2, where τ[v₁,v_i] is the prefix in the stream so far, and opt = min{|σ'|: d_F(σ',τ[v₁,v_i]) ≤ δ}. Let α = 2(d-1)⌊d/2⌋² + d. The working storage is O(ε^{-α}). Each vertex is processed in O(ε^{-α} log 1/ε) time for d ∈ {2,3} and O(ε^{-α}) time for d ≥ 4 . Thus, the whole τ can be simplified in O(ε^{-α}|τ| log 1/ε) time. Ignoring polynomial factors in 1/ε, this running time is a factor |τ| faster than the best static algorithm that offers the same guarantees.
We present another streaming algorithm that, for any integer k ≥ 2 and any ε ∈ (0,1/17), maintains a curve σ such that |σ| ≤ 2k-2 and d_F(σ,τ[v₁,v_i]) ≤ (1+ε) ⋅ min{d_F(σ',τ[v₁,v_i]): |σ'| ≤ k}, where τ[v₁,v_i] is the prefix in the stream so far. The working storage is O((kε^{-1}+ε^{-(α+1)})log 1/(ε)). Each vertex is processed in O(kε^{-(α+1)}log²1/(ε)) time for d ∈ {2,3} and O(kε^{-(α+1)} log 1/ε) time for d ≥ 4
A Theory of Sub-Barcodes
Get PDFThe primary tool in topological data analysis (TDA) is persistent homology, which involves computing a barcode - often from point-cloud or scalar field data - that serves as a topological signature for the underlying function. In this work, we introduce sub-barcodes and show how they arise naturally from factorizations of persistence module homomorphisms. We show that, as a partial order induced by factorizations, the relation of being a sub-barcode is strictly stronger than the rank invariant, and we apply sub-barcode theory to the problem of inferring information about the barcode of an unknown Lipschitz function from samples. The advantage of this approach is that it permits strong guarantees - with no noise - while requiring no sampling assumptions, and the resulting barcode is guaranteed to be a sub-barcode of every Lipschitz function that agrees with the data. We also present an algorithmic theory that allows for the efficient approximation of sub-barcodes using filtered Delaunay triangulations for Euclidean inputs
Improved Approximation Algorithms for Three-Dimensional Knapsack
Get PDFWe study the three-dimensional Knapsack (3DK) problem, in which we are given a set of axis-aligned cuboids with associated profits and an axis-aligned cube knapsack. The objective is to find a non-overlapping axis-aligned packing (by translation) of the maximum profit subset of cuboids into the cube. The previous best approximation algorithm is due to Diedrich, Harren, Jansen, Thöle, and Thomas (2008), who gave a (7+ε)-approximation algorithm for 3DK and a (5+ε)-approximation algorithm for the variant when the items can be rotated by 90 degrees around any axis, for any constant ε > 0. Chlebík and Chlebíková (2009) showed that the problem does not admit an asymptotic polynomial-time approximation scheme.
We provide an improved polynomial-time (139/29+ε) ≈ 4.794-approximation algorithm for 3DK and (30/7+ε) ≈ 4.286-approximation when rotations by 90 degrees are allowed. We also provide improved approximation algorithms for several variants such as the cardinality case (when all items have the same profit) and uniform profit-density case (when the profit of an item is equal to its volume). Our key technical contribution is container packing - a structured packing in 3D such that all items are assigned into a constant number of containers, and each container is packed using a specific strategy based on its type. We first show the existence of highly profitable container packings. Thereafter, we show that one can find near-optimal container packing efficiently using a variant of the Generalized Assignment Problem (GAP)
Persistent (Co)Homology in Matrix Multiplication Time
Get PDFMost algorithms for computing persistent homology do so by tracking cycles that represent homology classes. There are many choices of such cycles, and specific choices have found different uses in applications. Although it is known that persistence diagrams can be computed in matrix multiplication time for the more general case of zigzag persistent homology [Milosavljević et al., 2011], it is not clear how to extract cycle representatives, especially if specific representatives are desired. In this paper, we provide the same matrix multiplication bound for computing representatives for the two choices common in applications in the case of ordinary persistent (co)homology. We first provide a fast version of the reduction algorithm, which is simpler than the algorithm in [Milosavljević et al., 2011], but returns a different set of representatives than the standard algorithm [Edelsbrunner et al., 2002]. We then give a fast version of a variant called the row algorithm [De Silva et al., 2011], which returns the same representatives as the standard algorithm
Incremental Algorithm and Local Search for Minimum Non-Obtuse Triangulations (CG Challenge)
No full textIn this year’s CG challenge, the task was to compute a non-obtuse triangulation of given planar regions while minimizing the number of Steiner points. Our team (Gwamegi) used two approaches. The first approach incrementally adds Steiner points on the grid defined by the input points in the planar regions, while maintaining a Delaunay triangulation. The second approach is an iterated local search, which runs insertion and deletion steps alternatingly. In the insertion step, we add a new Steiner point inside a maximal convex subpolygon in the current triangulation. In the deletion step, we remove a number of Steiner points packed in a small region. We use both our approaches to obtain non-obtuse triangulations for all 150 instances. We use our second approach to reduce the number of Steiner points from the non-obtuse triangulations. We have successfully computed non-obtuse triangulations using a sufficiently small number of Steiner points for all instances
