[Tutorial] Space-Filling Curves for Mo's Algorithm

Правка en9, от dedsec_29, 2023-05-09 14:22:35

Ever since I read this blog, I have been curious to see how other space-filling curves other than Hilbert can be used to reduce the run time. In this blog, we will see how Peano curves can help bring down the run time of Mo's algorithm-based solutions.

Prerequisites: Mo's algorithm, Mo's algorithm using Hilbert Curve order

Relation to TSP

In Mo's algorithm, we try to come up with a comparator that can help us sort the queries in such a way that minimizes the total movement of L and R pointers. In other words, if we have $$$Q$$$ queries, each of the form $$$l_i$$$, $$$r_i$$$, then we wish to find such an arrangement of the queries that minimizes the following summation:

$$$S = \displaystyle\sum_{i=1}^{Q-1} |l_i - l_{i+1}| + |r_i - r_{i+1}|$$$.

Each query $$$(l,r)$$$ can be viewed as a coordinate on a 2D plane. We want to visit each of these points such that the travelled distance (with Manhattan distance as the distance metric) is minimized. This problem is the same as Traveling Salesman Problem (TSP), but a variant in which the salesman does not need to return to the starting city / point.

This problem is NP-Hard, taking exponential time to find the best minimum cost. However, we can trade-off time with accuracy. We can find a good enough solution which takes polynomial time and is fast enough. This is what space-filling curve based heuristic solutions help us achieve. Since the summation minimization problem is the same as TSP, we can apply the same heuristic approaches to Mo's algorithm. Let's try to find a new comparator based on all this information.

New Comparator

A comparator that uses Hilbert curve order has already been explained in this blog quite nicely. Here I will discuss a comparator that uses Peano curve order.

Let's build a Peano curve on a $$$3^k × 3^k$$$ matrix and visit all the cells on the matrix according to this curve. Denote ord(i, j, k) as the number of cells visited before the cell (i, j) in order of Peano curve on the $$$3^k × 3^k$$$ matrix. We sort the queries in non-descending order w.r.t. their value of ord(i,j,k).

Butz gives an algorithm for computing the Peano space-filling curve in terms of the base-3 representation of coordinates. It generalizes pretty well with higher dimensions. I will describe the algorithm briefly.

  1. List down the coordinates in base 3 representation. Each coordinate takes up k places in the base 3 / ternary representation. Here, we choose k such that k satisfies $$$3^k \geq N$$$
    Each row is a coordinate, taking up k places to write in ternary form. Let this matrix formed be denoted by $$$a$$$

  2. Perform $$$\text{peano-flip}$$$ on each $$$a_{i,j}$$$. It is a function that modifies $$$a_{i,j}$$$ values.
    $$$R2$$$ corresponds to the sum of values in columns left of column $$$j$$$ which are not in row $$$i$$$
    $$$R1$$$ corresponds to the sum of values in column $$$j$$$ above row $$$i$$$
    If $$$R1 + R2$$$ is odd, do: $$$a_{i,j} = 2 - a_{i,j}$$$
    Else we do nothing.

  3. Let ord(i,j,k) = num. Then, num is obtained by constructing a number off $$$a_{i,j}$$$ in base 10 in the following way:

For example, let's find Peano order for the query ()

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en18 Английский dedsec_29 2023-05-11 23:34:45 6 Tiny change: 'o see how other space-fil' -> 'o see how space-fil'
en17 Английский dedsec_29 2023-05-11 21:34:15 100 Tiny change: 'mit :D\n\n\n' -> 'mit :D\n\nThanks to [user:nor] for proof-reading the blog\n'
en16 Английский dedsec_29 2023-05-11 21:25:51 0 (published)
en15 Английский dedsec_29 2023-05-11 21:17:03 3151
en14 Английский dedsec_29 2023-05-10 17:50:48 380 Tiny change: 'q 8$. <br>\n![ ]' -> 'q 8$. <br><br>\n![ ]'
en13 Английский dedsec_29 2023-05-09 16:03:38 895 Tiny change: ' \sqrt{q})$\n\n# Use' -> ' \sqrt{q}).$\n\n# Use'
en12 Английский dedsec_29 2023-05-09 15:46:30 2725 Tiny change: ' 10^{6}$\n\n# Use ' -> ' 10^{6}$\n<br><br>\n\n# Use '
en11 Английский dedsec_29 2023-05-09 15:10:19 219 Tiny change: 'imgur.com/YojbCNS.png)\n![ ](https://i.imgur.com/' -> 'imgur.com/'
en10 Английский dedsec_29 2023-05-09 14:58:58 1211 Tiny change: ' k = 2 as 3^2 >= 8\n' -> ' k = 2 as $3^2$ >= 8\n'
en9 Английский dedsec_29 2023-05-09 14:22:35 103 Tiny change: 'ing way:\n\n' -> 'ing way:\n![ ](https://i.imgur.com/1MYmdIt.png)\n\n'
en8 Английский dedsec_29 2023-05-09 14:18:56 406 Tiny change: '4rS.png)\nEach row' -> '4rS.png)\n<br>\nEach row'
en7 Английский dedsec_29 2023-05-09 14:01:58 151 Tiny change: 'by $a$\n\n\n' -> 'by $a$\n\n2. Perform $\text{peano-flip} on each a_{i,j}$\n\n\n'
en6 Английский dedsec_29 2023-05-09 13:52:58 646
en5 Английский dedsec_29 2023-05-09 13:28:43 600 Tiny change: 'point.\n\nThis p' -> 'point.\n\n![ ](https://i.imgur.com/5uQUsDb.jpeg)\n\nThis p'
en4 Английский dedsec_29 2023-05-09 13:16:16 485 Tiny change: 'ach query (l,r) can be vi' -> 'ach query $(l,r)$ can be vi'
en3 Английский dedsec_29 2023-05-09 13:07:37 595
en2 Английский dedsec_29 2023-05-06 20:18:16 878
en1 Английский dedsec_29 2023-04-29 14:49:36 456 Initial revision (saved to drafts)