Algorithms for Coloring Quadtrees

Abstract. We describe simple linear time algorithms for coloring the squares of balanced and unbalanced quadtrees so that no two adjacent squares are given the same color. If squares sharing sides are defined as adjacent, we color balanced quadtrees with three colors, and unbalanced quadtrees with four colors; these results are both tight, as some quadtrees require this many colors. If squares sharing corners are defined as adjacent, we color balanced or unbalanced quadtrees with six colors; for some quadtrees, at least five colors are required.     

求图着色问题的新算法

图着色问题是NP-难度的问题。基于两种传统的启发式算法，提出了两种新的求解策略，由此给出了求图着色问题的两个新算法。与传统算法相比，其中一个新算法在时间复杂度不变的条件下，解的质量有明显提高；另一个则在时间复杂度稍有增加的前提下，进一步较显著地提高了所得解的质量。     

最大边染色的指数时间算法

最近,凤旺森,张立昂,曲婉玲,王捍贫对源于无线Mesh网络中的一个新的计算问题--最大边染色问题--提出了常数比近似算法.最大边染色问题要求对图的所有边染色,满足对任一顶点v,与其相关联的所有边所染的颜色种数不超过正整数q(q≥2),求使用颜色种数最多的染色方案.然而,他们并没有给出该问题的任何精确算法.提出了几个指数时间的精确算法并分析了它们的复杂度.对完全图可以在多项式时间内找到精确解.     

Approximation Algorithms for the Interval Constrained Coloring Problem

We consider the interval constrained coloring problem, which appears in the interpretation of experimental data in biochemistry. Monitoring hydrogen-deuterium exchange rates via mass spectroscopy experiments is a method used to obtain information about protein tertiary structure. The output of these experiments provides data about the exchange rate of residues in overlapping segments of the protein backbone. These segments must be re-assembled in order to obtain a global picture of the protein structure. The interval constrained coloring problem is the mathematical abstraction of this re-assembly process.     

基于超完美图着色的存储分配算法

为了提高性能,一些应用需要在编译时对主存进行针对性的管理.提出了基于超完美图的主存分配方法,其基本思想是通过生命周期分割将一般的相干图转换为超完美图,从而可以使用已有的线性时间的区间着色算法完成主存的分配.分别基于自底向上的积极生命周期分割策略和自顶向下的被动生命周期分割策略,实现了两个分配算法.初步评测表明,我们的分配算法是有效的编译时管理主存手段.     

An Experimental Analysis of Simple, Distributed Vertex Coloring Algorithms

We perform an extensive experimental evaluation of very simple, distributed, randomized algorithms for (Δ + 1) and so-called Brooks–Vizing vertex colorings, i.e., colorings using considerably fewer than Δ colors (here Δ denotes the maximum degree of the graph). We consider variants of algorithms known from the literature, boosting them with a distributed independent set computation. Our study clearly determines the relative performance of the algorithms with respect to the number of communication rounds and the number of colors. The results are confirmed by all the experiments and instance families. The empirical evidence shows that some algorithms use very few rounds and are rather effective, thus being amenable to be used in practice.     

An Experimental Analysis of Simple, Distributed Vertex Coloring Algorithms

We perform an extensive experimental evaluation of very simple, distributed, randomized algorithms for ( + 1) and so-called Brooks–Vizing vertex colorings, i.e., colorings using considerably fewer than colors (here denotes the maximum degree of the graph). We consider variants of algorithms known from the literature, boosting them with a distributed independent set computation. Our study clearly determines the relative performance of the algorithms with respect to the number of communication rounds and the number of colors. The results are confirmed by all the experiments and instance families. The empirical evidence shows that some algorithms use very few rounds and are rather effective, thus being amenable to be used in practice.     

A Constant-Time Algorithm for Finding Neighbors in Quadtrees

Quadtrees and linear quadtrees are well-known hierarchical data structures to represent square images of size 2^{r} times 2^{r}. Finding the neighbors of a specific leaf node is a fundamental operation for many algorithms that manipulate quadtree data structures. In quadtrees, finding neighbors takes O(r) computational time for the worst case, where r is the resolution (or height) of a given quadtree. Schrack [1] proposed a constant-time algorithm for finding equal-sized neighbors in linear quadtrees. His algorithm calculates the location codes of equal-sized neighbors; it says nothing, however, about their existence. To ensure their existence, additional checking of the location codes is needed, which usually takes O(r) computational time. In this paper, a new algorithm to find the neighbors of a given leaf node in a quadtree is proposed which requires just O(1) (i.e., constant) computational time for the worst case. Moreover, the algorithm takes no notice of the existence or nonexistence of neighbors. Thus, no additional checking is needed. The new algorithm will greatly reduce the computational complexities of almost all algorithms based on quadtrees.     

Quadtrees, Transforms and Image Coding

Transforms and quadtrees are both methods of representing information in an image in terms of the presence of information at differing length scales. This paper presents a mathematical relationship between these two approaches to describing images in the particular case when Walsh transforms are used. Furthermore, both methods have been used for the compression of images for transmission. This paper notes that under certain circumstances, quadtree compression produces identical results to Walsh transform coding, but requires less computational effort to do so. Remarks are also made about the differences between these approaches.     

Window Query Processing in Linear Quadtrees

The linear quadtree is a spatial access method that is built by decomposing the spatial objects in a database into quadtree blocks and storing these quadtree blocks in a B-tree. The linear quadtree is very useful for geographic information systems because it provides good query performance while using existing B-tree implementations. An algorithm and a cost model are presented for processing window queries in linear quadtrees. The algorithm can handle query windows of any shape in the general case of spatial databases with overlapping objects. The algorithm recursively decomposes the space into quadtree blocks, and uses the quadtree blocks overlapping the query window to search the B-tree. The cost model estimates the I/O cost of processing window queries using the algorithm. The cost model is also based on a recursive decomposition of the space, and it uses very simple parameters that can easily be maintained in the database catalog. Experiments with real and synthetic data sets verify the accuracy of the cost model.     

一种基于四叉树结构的排料算法

提出了一种利用四叉树结构来描述矩形物体排料过程的算法。为了确保排料布局的合理性，满足工业上的一刀切要求，需采用组合规则和邻接规则来合成矩形块，这样做还可减少废料碎片、降低算法复杂度、提高板材利用率。     

用四叉树算法建立自主系统环境模型

对环境建模是自主系统路径规划的基础,针对传统方法中存在的种种缺陷,该文在阐述自主系统中利用激光测距成像雷达的坐标变换法所获取的距离图实时检测障碍物的基础上,利用二值图像的四叉树表示是基于数据区域的一致性判别准则和空间递归分解原理建立起来的一种分层的树形数据结构,将一幅二值图像分为大小相同的四个分区,着重研究了利用模式四叉树建立部分已知或完全未知的环境模型的方法,结果显示其节省了四叉树占用的存储空间,在相同的存储空间情况下,提高了环境分辨率,加快了系统的运行速度,并给出了环境信息的优化策略。     

Strong Conflict-Free Coloring for Intervals

We consider the \(k\) -strong conflict-free ( \(k\) -SCF) coloring of a set of points on a line with respect to a family of intervals: Each point on the line must be assigned a color so that the coloring is conflict-free in the following sense: in every interval \(I\) of the family there are at least \(k\) colors each appearing exactly once in \(I\) . We first present a polynomial-time approximation algorithm for the general problem; the algorithm has approximation ratio 2 when \(k=1\) and \(5-\frac{2}{k}\) when \(k\ge 2\) . In the special case of a family that contains all possible intervals on the given set of points, we show that a 2-approximation algorithm exists, for any \(k \ge 1\) . We also provide, in case \(k=O({{\mathrm{polylog}}}(n))\) , a quasipolynomial time algorithm to decide the existence of a \(k\) -SCF coloring that uses at most \(q\) colors.