Linear-time border-tracing algorithms for quadtrees

In applications where the quadtree is used as an underlying object representation, a number of basic operations are implemented as a trace along the border of the object's region. A technique is presented that determines a way to shift any given scene (as well as its quadtree), so that the border of all the objects in the scene can be traversed in time proportional to the length of all the borders in the scene (or the number of blocks when the scene is represented as a quadtree). This determination is shown to be performed in time proportional to the length of all the borders in the scene. This allows the direct translation of a number of chain-code algorithms into quadtree algorithms without loss of asymptotic worst-case efficiency. This results in improved worst-case analyses of algorithms that convert chain codes into quadtrees and that perform connected component labeling of images represented as quadtrees.     

Analytic variations on quadtrees

Quadtrees constitute a hierarchical data structure which permits fast access to multidimensional data. This paper presents the analysis of the expected cost of various types of searches in quadtrees — fully specified and partial-match queries. The data model assumes random points with independently drawn coordinate values.The analysis leads to a class of full-history divide-and-conquer recurrences. These recurrences are solved using generating functions, either exactly for dimensiond=2, or asymptotically for higher dimensions. The exact solutions involve hypergeometric functions. The general asymptotic solutions rely on the classification of singularities of linear differential equations with analytic coefficients, and on singularity analysis techniques.These methods are applicable to the asymptotic solution of a wide range of linear recurrences, as may occur in particular in the analysis of multidimensional searching problems.The work of Philippe Flajolet was supported in part by the Basic Research Action of the E.C. under Contract No. 3075 (Project ALCOM). A preliminary version of this paper has been presented in the form of an extended abstract at the Second Annual Symposium on Discrete Algorithms [13].     

Shape approximation using quadtrees

The quadtree representation encodes a 2″ by 2″ binary image as a set of maximal blocks of 1's or 0's whose sizes and positions are powers of 2. With the aid of the quadtree, a hierarchy of approximations to the image can be defined. Several ways of doing this are described. The accuracy of these approximations is empirically evaluated by studying how fast estimates of the first few moments of the image, computed from the approximations, converge to the true values, using a database of 112 airplane silhouettes. Approaches to the problem of fast shape matching using these approximations are also discussed.     

Evaluation of connected-component labeling algorithms for distributed-memory systems

Connected component labeling is a key step in a wide-range of applications, such as community detection in social networks and coherent structure identification in massively-parallel scientific simulations. There have been several distributed-memory connected component algorithms described in literature; however, little has been done regarding their scalability analysis. Theoretical and experimental results are presented for five algorithms: three that are direct implementations of previous approaches, one that is an implementation of a previous approach that is optimized to reduce communication, and one that is a novel approach based on graph contraction. Under weak scaling and for certain classes of graphs, the graph contraction algorithm scales consistently better than the four other algorithms. Furthermore, it uses significantly less memory than two of the alternative methods and is of the same order in terms of memory as the other two.     

基于四叉树的三维地形模拟的LOD算法

细节层次显示和简化技术（LOD技术）是实时真实感图形学技术中应用比较多的一个技术,通过这种技术可以较好地简化场景的复杂度,同时对图形真实度损失很少,并满足一定的实时性.在众多文献所提到的LOD算法中,一种比较常用的算法就是基于四叉树的LOD算法,这种算法的基本思想极为简单,即利用一个距离的阈值来控制四叉树递归运算的深度,当这个阈值比较大时,得到较少的三角面片数量,反之则得到较多的三角面片.文中实验也是采用了这种方法进行LOD的计算.文中还讲述了LOD技术的原理以及算法实现,探讨了LOD算法的实现中的问题和改进的方法,研究了节点评价系统的改进方法,最后展望了LOD技术的进一步发展.     

Efficient approximation algorithms for the routing open shop problem

We consider the routing open shop problem being a generalization of two classical discrete optimization problems: the open shop scheduling problem and the metric traveling salesman problem. The jobs are located at nodes of some transportation network, and the machines travel on the network to execute the jobs in the open shop environment. The machines are initially located at the same node (depot) and must return to the depot after completing all the jobs. It is required to find a non-preemptive schedule with the minimum makespan. The problem is NP-hard even on the two-node network with two machines. We present new polynomial-time approximation algorithms with worst-case performance guarantees.     

矩形NAM图像表示及其上的连通区域标记算法

既能减少数据量又能直接快速地进行运算是图像表示方法所追求的目标。本文为克服传统的图像层次结构限制条件过多的缺陷,在借鉴Packing问题的思想的基础上,提出了非对称逆布局模式表示模型（Non-Symmetry and Anti-Packing Pattern Representation Model,NAM）。NAM模型的非对称层次结构使其在表示一幅图像时没有过多的限制条件,因此可以获得更高的压缩比,而且它可以直接进行某些图像处理运算,其基于像素块的运算方式使它的运算效率更高,矩形NAM图像表示和基于它的连通区域标记算法证明了这一点。     

Fast neighborhood operations for images and volume data sets

This paper presents a new approach to carry out erosion, dilation and connected component labeling. We use the extreme vertices model, an orthogonal polyhedra representation, to describe binary images and volume data sets in a very efficient way.

Our proposal does not use a voxel-based approach but deals with the inner sections of the object. It allows to treat images and volumes indistinctly using the same algorithm and data structure with no overhead of memory and can be applied to manifold as well as non-manifold data. The connected component labeling algorithm actually detects non-manifold zones and permits to break or not the objects at these zones by an user-specified parameter.     

Complexity and algorithms for two-stage flexible flowshop scheduling with availability constraints

This paper considers the two-stage flexible flowshop scheduling problem with availability constraints. We discuss the complexity and the approximability of the problem, and provide some approximation algorithms with finite and tight worst case performance bounds for some special cases of the problem.     

Linear-time algorithms for problems on planar graphs with fixed disk dimension

The disk dimension of a planar graph G is the least number k for which G embeds in the plane minus k open disks, with every vertex on the boundary of some disk. Useful properties of graphs with a given disk dimension are derived, leading to an algorithm to obtain an outerplanar subgraph of a graph with disk dimension k by removing at most 2k−2 vertices. This reduction is used to obtain linear-time exact and approximation algorithms on graphs with fixed disk dimension. In particular, a linear-time approximation algorithm is presented for the pathwidth problem.     

Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons

Given a triangulation of a simple polygonP, we present linear-time algorithms for solving a collection of problems concerning shortest paths and visibility withinP. These problems include calculation of the collection of all shortest paths insideP from a given source vertexS to all the other vertices ofP, calculation of the subpolygon ofP consisting of points that are visible from a given segment withinP, preprocessingP for fast "ray shooting" queries, and several related problems.     

Connected component labeling on a 2D grid using CUDA

Connected component labeling is an important but computationally expensive operation required in many fields of research. The goal in the present work is to label connected components on a 2D binary map. Two different iterative algorithms for doing this task are presented. The first algorithm (Row-Col Unify) is based upon the directional propagation labeling, whereas the second algorithm uses the Label Equivalence technique. The Row-Col Unify algorithm uses a local array of references and the reduction technique intrinsically. The usage of shared memory extensively makes the code efficient. The Label Equivalence algorithm is an extended version of the one presented by Hawick et al. (2010) [3]. At the end the comparison depending on the performances of both of the algorithms is presented.     

Worst-case performance of critical path type algorithms

The critical path method remains one of the most popular approaches in practical scheduling. Being developed for the makespan problem this method can also be generalized to the maximum lateness problem. For the unit execution time task system and parallel processors this generalization is known as the Brucker–Garey–Johnson algorithm. We characterize this algorithm by introducing an upper bound on the deviation of the criterion from its optimal value. The bound is stated in terms of parameters characterizing the problem, namely number of processors, the length of the longest path, and the total required processing time. We also derive a similar bound for the preemptive version of the Brucker– Garey–Johnson algorithm.     

Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons

Given a triangulation of a simple polygonP, we present linear-time algorithms for solving a collection of problems concerning shortest paths and visibility withinP. These problems include calculation of the collection of all shortest paths insideP from a given source vertexS to all the other vertices ofP, calculation of the subpolygon ofP consisting of points that are visible from a given segment withinP, preprocessingP for fast "ray shooting" queries, and several related problems.Work on this paper by this author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, the IBM Corporation, and from the U.S.-Israel Binational Science Foundation.Work on this paper by this author has been supported by National Science Foundation Grant DCR-86-05962.     

Independency relationships and learning algorithms for singly connected networks

Graphical structures such as Bayesian networks or Markov networks are very useful tools for representing irrelevance or independency relationships, and they may be used to efficiently perform reasoning tasks. Singly connected networks are important specific cases where there is no more than one undirected path connecting each pair of variables. The aim of this paper is to investigate the kind of properties that a dependency model must verify in order to be equivalent to a singly connected graph structure, as a way of driving automated discovery and construction of singly connected networks in data. The main results are the characterizations of those dependency models which are isomorphic to singly connected graphs (either via the d-separation criterion for directed acyclic graphs or via the separation criterion for undirected graphs), as well as the development of efficient algorithms for learning singly connected graph representations of dependency models.     

Weighted principal component extraction with genetic algorithms

Pattern recognition techniques have been widely used in a variety of scientific disciplines including computer vision, artificial intelligence, biology, and so forth. Although many methods present satisfactory performances, they still have several weak points, thus leaving a lot of space for further improvements. In this paper, we propose two performance-driven subspace learning methods by extending the principal component analysis (PCA) and the kernel PCA (KPCA). Both methods adopt a common structure where genetic algorithms are employed to pursue optimal subspaces. Because the proposed feature extractors aim at achieving high classification accuracy, enhanced generalization ability can be expected. Extensive experiments are designed to evaluate the effectiveness of the proposed algorithms in real-world problems including object recognition and a number of machine learning tasks. Comparative studies with other state-of-the-art techniques show that the methods in this paper are capable of enhancing generalization ability for pattern recognition systems.