Succinct Data Structures for Baxter Permutation and Related Families
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913517336002560 |
|---|---|
| author | Chakraborty, Sankardeep Jo, Seungbum Kim, Geunho Sadakane, Kunihiko |
| author_facet | Chakraborty, Sankardeep Jo, Seungbum Kim, Geunho Sadakane, Kunihiko |
| contents | A permutation $π: [n] \rightarrow [n]$ is a Baxter permutation if and only if it does not contain either of the patterns $2-41-3$ and $3-14-2$. Baxter permutations are one of the most widely studied subclasses of general permutation due to their connections with various combinatorial objects such as plane bipolar orientations and mosaic floorplans, etc. In this paper, we introduce a novel succinct representation (i.e., using $o(n)$ additional bits from their information-theoretical lower bounds) for Baxter permutations of size $n$ that supports $π(i)$ and $π^{-1}(j)$ queries for any $i \in [n]$ in $O(f_1(n))$ and $O(f_2(n))$ time, respectively. Here, $f_1(n)$ and $f_2(n)$ are arbitrary increasing functions that satisfy the conditions $ω(\log n)$ and $ω(\log^2 n)$, respectively. This stands out as the first succinct representation with sub-linear worst-case query times for Baxter permutations.
Additionally, we consider a subclass of Baxter permutations called \textit{separable permutations}, which do not contain either of the patterns $2-4-1-3$ and $3-1-4-2$. In this paper, we provide the first succinct representation of the separable permutation $ρ: [n] \rightarrow [n]$ of size $n$ that supports both $ρ(i)$ and $ρ^{-1}(j)$ queries in $O(1)$ time. In particular, this result circumvents Golynski's [SODA 2009] lower bound result for trade-offs between redundancy and $ρ(i)$ and $ρ^{-1}(j)$ queries.
Moreover, as applications of these permutations with the queries, we also introduce the first succinct representations for mosaic/slicing floorplans, and plane bipolar orientations, which can further support specific navigational queries on them efficiently. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_16650 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Succinct Data Structures for Baxter Permutation and Related Families Chakraborty, Sankardeep Jo, Seungbum Kim, Geunho Sadakane, Kunihiko Data Structures and Algorithms A permutation $π: [n] \rightarrow [n]$ is a Baxter permutation if and only if it does not contain either of the patterns $2-41-3$ and $3-14-2$. Baxter permutations are one of the most widely studied subclasses of general permutation due to their connections with various combinatorial objects such as plane bipolar orientations and mosaic floorplans, etc. In this paper, we introduce a novel succinct representation (i.e., using $o(n)$ additional bits from their information-theoretical lower bounds) for Baxter permutations of size $n$ that supports $π(i)$ and $π^{-1}(j)$ queries for any $i \in [n]$ in $O(f_1(n))$ and $O(f_2(n))$ time, respectively. Here, $f_1(n)$ and $f_2(n)$ are arbitrary increasing functions that satisfy the conditions $ω(\log n)$ and $ω(\log^2 n)$, respectively. This stands out as the first succinct representation with sub-linear worst-case query times for Baxter permutations. Additionally, we consider a subclass of Baxter permutations called \textit{separable permutations}, which do not contain either of the patterns $2-4-1-3$ and $3-1-4-2$. In this paper, we provide the first succinct representation of the separable permutation $ρ: [n] \rightarrow [n]$ of size $n$ that supports both $ρ(i)$ and $ρ^{-1}(j)$ queries in $O(1)$ time. In particular, this result circumvents Golynski's [SODA 2009] lower bound result for trade-offs between redundancy and $ρ(i)$ and $ρ^{-1}(j)$ queries. Moreover, as applications of these permutations with the queries, we also introduce the first succinct representations for mosaic/slicing floorplans, and plane bipolar orientations, which can further support specific navigational queries on them efficiently. |
| title | Succinct Data Structures for Baxter Permutation and Related Families |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.16650 |