# 一个 Treemap 的近似绘制算法

# 符号定义

对一个矩形 $r$, 令 $h(r)$ 为其高，$w(r)$ 为其宽。于是其面积为 $a(r):=h(r)w(r)$，其周长为 $p(r) := h(r) + w(r)$，纵横比为 $\rho(r):=\frac{\max\{h(r),w(r)\}}{\min\{h(r),w(r)\}}$. 若集合 $\mathscr R=\{r_i|i=1,2,\dots,n\}$，定义其周长和 $ps(\mathscr{R}) := \sum_{r \in \mathscr{R}}p(r)$, 其最大周长 $pm(\mathscr{R}):=\max_{r \in \mathscr{R}}p(r)$, 其最大长宽比为 $\rho(\mathscr{R}) := \max_{r\in\mathscr{R}} \rho(r)$. (由于周长和半周长之间只相差一个常系数，因此是无关紧要的。为方便，我们姑且称其为周长。)

# 问题

对于矩形的分划，先前已有三个基本的问题作为铺垫：

• 如何将原矩形 $R_0$ 划分成矩形集 $\mathscr{R}$, 使得周长和 $ps(\mathscr{R})$ 最小。称为周长和最小问题 (PERI-SUM)。
• 如何将原矩形 $R_0$ 划分成矩形集 $\mathscr{R}$, 使得最大周长 $pm(\mathscr{R})$ 最小。称为最大周长最小问题 (PERI-MAX)。
• 如何将原矩形 $R_0$ 划分成矩形集 $\mathscr{R}$, 使得最大长宽比 $\rho(\mathscr{R})$ 最小。称为最大长宽比最小问题 (ASPECT-RATIO)。

以上三个问题都是 NP-hard 问题 。

而本篇论文中的算法，可以在$O(n\log n)$ 复杂度内使矩形的划分$\mathscr{R}$ 同时达到：

• PERI-SUM 问题的$\frac{2}{\sqrt{3}}$ 倍最优解
• PERI-MAX 问题的$1.25$ 倍最优解
• ASPECT-RATIO 问题中，控制$\rho(\mathscr{R}) \leq \max\{\rho(R_0),3,1+\max_{i=1,\dots,n-1}\frac{a_{i+1}}{a_i}\}$

# 算法过程及分析

首先，我们引入一个引理，以说明算法的每一步操作的结果及其性质。

引理 1 令$A=\{b_1,b_2,\dots,b_m\}$，其中$b_i \leq b_{i+1},\,i=1,2,\dots,m-1$。令$\alpha = \sum_{i=1}^mb_i$，则$\exists k \in \mathbb{Z}$ 使得$\sum_{i=1}^{k-1}b_i < \frac{\alpha}{3} \leq \sum_{i=1}^kb_i$。于是以下两结论之一必成立：

1. $\frac{\alpha}{3} \leq b_m$
2. $b_m<\frac{\alpha}{3}$，$k\leq m-2$ 且$\sum_{i=1}^kb_i<\frac{5\alpha}{9}$(且当$b_{m-1} \leq \frac{\alpha}{6}$ 时，$\sum_{i=1}^kb_i < \frac{\alpha}{2}$)

根据简单的大小估计和放缩就可以证明了。

# 算法

输入：一个矩形$R$，一个正实数集合$A:= \{a_i,a_{i+1},\dots,a_{i+|A|-1}\}$，满足$|A| \geq 2$，$a_i\leq a_{i+1} \leq \cdots \leq a_{i+|A|-1}$ 且$\sum_{a \in A} = a(R)$。在不失一般性的前提下，假设$h(R) \leq w(R)$。

输出：一个关于$R$ 的划分$\{r_i,r_{i+1},\dots,r_{i+|A|-1}\}$。

我把代码写成了类似 Python 的伪代码形式

def dissect(R,A):

    if len(A) > 1:

        if sum(A)/3 <= max(A):

            A1 = [a[i],a[i+1],...,a[i+len(A)-2]]

            A2 = [a[i+len(A)-1]]

        else:

            k = 0

            A1 = []

            while sum(A1) < sum(A)/3:

                A1.append(a[i+k])

        h(R1) = h(R2) = h(R)

        w(R1) = w(R)*sum(A1)/sum(A)

        w(R2) = w(R)*sum(A2)/sum(A)

        return dissect(R1,A1).extend(dissect(R2,A2))

        # repeated the recursive process until the A has only one element 

    else:

        return R # while len(A) = 1, return the rectangle

# 算法的复杂度

引理 2 给定一个矩形$R_0$ 和一个包含$n$ 个正实数的集合$A_0$，使得$\sum_{a \in A_0} a = a(R_0)$，则函数 dissect(R0,A0) 返回一个关于$A_0$ 的划分需要的时间复杂度为$O(n\log n)$。

根据算法的内容来看，复杂度是显然的。

定理 1 给定一个矩形$R_0$ 和一个包含$n$ 个正实数的集合$A_0=\{a_1,a_2,\dots,a_n\}$，使得$\sum_{a \in A}a = a(R_0)$，令$\mathscr{R}=\{r_1,r_2,\dots,r_n\}$ 为 dissect(R0,A0) 的输出结果，其中$a(r_i) = a_i,a_i \in A_0$。令$\mathscr{R}'$ 为递归过程中得到的全体矩形组成的集合，则有：

1. 对任一$r \in \mathscr{R} \cup \mathscr{R}'$，有

$$\rho(r) \leq \max\left\{\rho(R_0),3,1+\max_{i=1,2,\dots,n-1}\frac{a_{i=1}}{a_i}\right\}.$$

2. 设划分得到的最大周长 (PERI-MAX) 最小值为$OPT_{pm}$，则

$$\frac{ps(\mathscr{R})}{OPT_{pm}} \leq \frac{2}{\sqrt{3}}(\approx 1.1547).$$

3. 设划分得到的周长和最小值为$OPT_{ps}$，则

$$\frac{ps(\mathscr{R})}{OPT_{ps}} \leq \frac{5}{4}.$$

# 对纵横比 (ASPECT-RATIO) 的分析

引理 1 令$R_1$ 和$R_2$ 是一个复合矩形$R\in\mathscr R$ 的左右孩子，设$a_l\leq a_{l+1} \leq \cdots \leq a_m$ 是$A(R)$ 中的实数。