Range Queries for Permutation Pattern Matching: Separations, Equivalences, and Applications

The problem of Permutation Pattern Matching (PPM) asks, given a permutation $\pi :[n]\to [n]$, viewed as the point set $P=\{(i,\pi (i)):i\in [n]\}$, and a pattern $\sigma$ of small length $k$, whether $P$ contains an order-isomorphic copy of $\sigma$. The PPM problem and its (exact and approximate) counting variants have been studied extensively in the literature. We consider a preprocessing-query version: after preprocessing $P$, one must determine whether a query $P^{\mathrm{\prime }}\subseteq P$ contains $\sigma$, where $P^{\mathrm{\prime }}$ is obtained by intersecting $P$ with a geometric shape (e.g., an axis-aligned rectangle or $k$ such rectangles). This naturally generalizes the classical range query problem in computational geometry, which corresponds to the case $\mathrm{\mid }\sigma \mathrm{\mid }=1$. We extend the study of this problem from patterns of length $2$ to patterns of length $3$ (and in some cases beyond), and prove new fine-grained equivalences, separations, and applications: (1) Single rectangle: For all patterns of length $3$, detection can be done with $\tilde{O}(n)$ preprocessing and $\tilde{O}(1)$ query time. The proof goes through a new tool of independent interest: reductions from rectangle queries to a simpler family of slab queries. (2) Multiple rectangles: For $\sigma =132$, detection is equivalent to the online set disjointness problem; we also show connections to online $k$-set disjointness. To our knowledge, this is the first equivalence between a PPM-type problem and online set disjointness, a problem playing a fundamental role in fine-grained complexity. (3) Counting: As applications, we obtain an $O(n^{1.725})$ time algorithm for exact counting of $5$-patterns based on the rectangle-to-slab reduction, improving upon [Beniamini and Lavee, ICALP 2025], and an $\tilde{O}(n^{7\mathrm{/}4})$ approximate counting algorithm for $6$-patterns, the first to break the $O(n^2)$ barrier for $6$-patterns.