Connected searching of weighted trees

In this paper we consider the problem of connected edge searching of weighted trees. Barrière et al. claim in [L. Barrière, P. Flocchini, P. Fraigniaud, N. Santoro, Capture of an intruder by mobile agents, in: SPAA’02: Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, ACM, New York, NY, USA, 2002, pp. 200-209] that there exists a polynomial-time algorithm for finding an optimal search strategy, that is, a strategy that minimizes the number of used searchers. However, due to some flaws in their algorithm, the problem turns out to be open. It is proven in this paper that the considered problem is strongly NP-complete even for node-weighted trees (the weight of each edge is 1) with one vertex of degree greater than 2. It is also shown that there exists a polynomial-time algorithm for finding an optimal connected search strategy for a given bounded degree tree with arbitrary weights on the edges and on the vertices. This is an FPT algorithm with respect to the maximum degree of a tree.     

Adaptive searching in succinctly encoded binary relations and tree-structured documents

The methods most heavily used by search engines to answer conjunctive queries on binary relations (such as one associating keywords with web-pages) are based on computing the intersection of postings lists stored as sorted arrays and using variants of binary search. We show that a succinct representation of the binary relation permits much better results, while using less space than traditional methods. We apply our results not only to conjunctive queries on binary relations, but also to queries on semi-structured documents such as XML documents or file-system indexes, using a variant of an adaptive algorithm used to solve conjunctive queries on binary relations.     

Multidimensional heaps and complementary range searching

We discuss multidimensional heaps, that is, heaps in which each element has a d-tuple of keys and we can find and delete the minimum element for each coordinate. These structures are a reasonable generalization of double-ended heaps, and can be realized with O(1) insert, merge, findmin and O(logn) deletemin, or with O(logn) insert, and O(1) findmin, deletemin, all these times being worst-case. We also apply these structures to the problem of complementary range searching, improving on the performance of d-dimensional interval heaps introduced by van Leeuwen and West.     

Decomposition and intersection of simple splinegons

A splinegon is a polygon whose edges have been replaced by well-behaved curves. We show how to decompose a simple splinegon into a union of monotone pieces and into a union of differences of unions of convex pieces. We also show how to use a fast triangulation algorithm to test whether two given simple splinegons intersect. We conclude with examples of splinegons that make the extension of algorithms from polygons to splinegons difficult.Work on this paper by David A. Dobkin and Diane L. Souvaine was partially supported by National Science Foundation Grants MCS 83-03926 and DCR 85-05517. Diane L. Souvaine was also partially supported by an Exxon Foundation Fellowship.     

Lower bounds for set intersection queries

We consider the followingset intersection reporting problem. We have a collection of initially empty sets and would like to process an intermixed sequence ofn updates (insertions into and deletions from individual sets) andq queries (reporting the intersection of two sets). We cast this problem in thearithmetic model of computation of Fredman [F1] and Yao [Ya2] and show that any algorithm that fits in this model must take time (q+nq) to process a sequence ofn updates andq queries, ignoring factors that are polynomial in logn. We also show that this bound is tight in this model of computation, again to within a polynomial in logn factor, improving upon a result of Yellin [Ye]. Furthermore, we consider the caseq=O(n) with an additional space restriction. We only allow the use ofm memory locations, wherem n^3/2. We show a tight bound of (n²/m^1/3) for a sequence ofn operations, again ignoring the polynomial in logn factors.     

A note on predecessor searching in the pointer machine model

Predecessor searching is a fundamental data structuring problem and at the core of countless algorithms: given a totally ordered universe U with n elements, maintain a subset S⊆U such that for each element x∈U its predecessor in S can be found efficiently. During the last thirty years the problem has been studied extensively and optimal algorithms in many classical models of computation are known. In 1988, Mehlhorn et al. [K. Mehlhorn, S. Näher, H. Alt, A lower bound on the complexity of the union-split-find problem, SIAM J. Comput. 17 (6) (1988) 1093-1102] showed an amortized lower bound of Ω(loglogn) in the pointer machine model. We give a different proof for this bound which sheds new light on the question of how much power the adversary actually needs.     

微装配中零部件搜索方法

针对如何快速且准确地在微装配的显微视野中寻找到目标零部件,并获取目标零部件的全局视觉信息的问题,提出了一种基于显微视觉倍率切换的微装配零部件搜索机制.详细分析了如何确定自动搜索步长;论述了自动搜索策略的原理与过程:通过自动扫描目标平面,以准确识别出目标平面内的微零部件,有效地克服了大范围微装配中显微视觉范围远小于操作域的局限性,保证了微装配零部件目标始终呈现在不同显微倍率视野中,为微装配机器人的进一步操作奠定了视觉基础.实验结果表明:提出的搜索方法搜索成功率达到了95％,平均搜索时间为28 s.     

On the cost of searching signature trees

A precise analysis of the retrieval of signature trees is presented. A signature tree is a data structure constructed over a signature file to speed up searching all those signatures, which match a given query signature. The methods used include a detailed study of probabilistic analysis in conjunction with suitable contour integration of complex variabled functions.     

Detecting the intersection of two convex shapes by searching on the 2-sphere

We take a look at the problem of deciding whether two convex shapes intersect or not. We do so through the well known lens of Minkowski sums and with a bias towards applications in computer graphics and robotics. We describe a new technique that works explicitly on the unit sphere, interpreted as the sphere of directions. In extensive benchmarks against various well-known techniques, ours is found to be slightly more efficient, much more robust and comparatively easy to implement. In particular, our technique is compared favorably to the ubiquitous algorithm of Gilbert, Johnson and Keerthi (GJK), and its decision variant by Gilbert and Foo. We provide an in-depth geometrical understanding of the differences between GJK and our technique and conclude that our technique is probably a good drop-in replacement when one is not interested in the actual distance between two non-intersecting shapes.     

Fast dynamic intersection searching in a set of isothetic line segments

We reconsider the (isothetic) line segment intersection searching problem: Given a set S of n horizontal and vertical line segments and a query segment q, find all t segments in S intersecting q. We describe the first dynamic solution for this problem which achieves O(log n + t) query time. This, however, has to be paid by O(n log² n) space requirements and O(log³ n) update time. If segments are defined over a grid of size N × N (the semidynamic case), then the problem can be solved in O(logN + t) query time, O(n log² N) space and O(log² N) update time. The solution is based on the use of segment tree and range tree and the halfobject technique.     

Randomized splay trees: Theoretical and experimental results

Splay trees are self-organizing binary search trees that were introduced by Sleator and Tarjan [J. ACM 32 (1985) 652-686]. In this paper we present a randomized variant of these trees. The new algorithm for reorganizing the tree is both simple and easy to implement. We prove that our randomized splaying scheme has the same asymptotic performance as the original deterministic scheme but improves constants in the expected running time. This is interesting in practice because the search time in splay trees is typically higher than the search time in skip lists and AVL-trees. We present a detailed experimental study of our algorithm. On request sequences generated by fixed probability distributions, we can achieve improvements of up to 25% over deterministic splaying. On request sequences that exhibit high locality of reference, the improvements are minor.     

Edge and node searching problems on trees

In this paper, we consider the edge searching and node searching problems on trees. Given a tree, we show a transformation from an optimal node-search strategy to an optimal edge-search strategy. Using our transformation, we simplify a previous linear-time algorithm for determining the edge-search number of a tree, and improve the running time of a previous algorithm for constructing an optimal edge-search strategy of an n-vertex tree from O(nlogn) to O(n). We also improve the running time of a previous algorithm for constructing an optimal min-cut linear layout of an n-vertex tree with the maximum degree 3 from O(nlogn) to O(n).     

Bernstein Bezoutians and application to intersection problems

We study the Bézier curve-surface and Bézier surface-surface intersection problems avoiding the well-known unstable conversion between the Bernstein basis and the power basis. These varieties are given by parameterizations in Bernstein bases and all intermediate computations are performed in that form. For this purpose we construct an adapted resultant for generic Bernstein polynomial systems with a special shape which appear in the intersection problems. This construction is based on the expression of the Bezoutian matrix in Bernstein form.     

二叉树的一种新存储结构

本文提出了一种可简单、高效地表示二叉树的存储结构。该结构：（１）显著地提高了寻找给定结点的父／兄结点等基本操作的时间效率，达到Ｏ（１），高于传统结构树下的效率；（２）使遍历操作不再显式或隐式地使用辅助堆栈；（３）提高了存储结构中指针字段利用率；（４）保持其它基本操作的效率不变。     

Rank and select revisited and extended

The deep connection between the Burrows–Wheeler transform (BWT) and the so-called rank and select data structures for symbol sequences is the basis of most successful approaches to compressed text indexing. Rank of a symbol at a given position equals the number of times the symbol appears in the corresponding prefix of the sequence. Select is the inverse, retrieving the positions of the symbol occurrences. It has been shown that improvements to rank/select algorithms, in combination with the BWT, turn into improved compressed text indexes.     

Red-black trees with relative node keys

This paper addresses the problem of storing an ordered list using a red-black tree, where node keys can only be expressed relative to each other. The insert and delete operations in a red-black tree are extended to maintain the relative key values. The extensions rely only on relative keys of neighboring nodes, adding constant overhead and thus preserving the logarithmic time complexity of the original operations.