Fast computation of smallest enclosing circle with center on a query line segment

Here we propose an efficient algorithm for computing the smallest enclosing circle whose center is constrained to lie on a query line segment. Our algorithm preprocesses a given set of n points P={p₁,p₂,…,pn} such that for any query line or line segment L, it efficiently locates a point c on L that minimizes the maximum distance among the points in P from c. Roy et al. [S. Roy, A. Karmakar, S. Das, S.C. Nandy, Constrained minimum enclosing circle with center on a query line segment, in: Proc. of the 31st Mathematical Foundation of Computer Science, 2006, pp. 765-776] have proposed an algorithm that solves the query problem in O(log²n) time using O(nlogn) preprocessing time and O(n) space. Our algorithm improves the query time to O(logn); but the preprocessing time and space complexities are both O(n²).     

Quasi-optimal upper bounds for simplex range searching and new zone theorems

This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a setP ofn points in ?^d so that, given any query simplexq, the points inP ∩q can be counted or reported efficiently. Ifm units of storage are available (n <m <n ^d ), then we show that it is possible to answer any query inO(n ^1+?/m ^1/d ) query time afterO(m ^1+?) preprocessing. This bound, which holds on a RAM or a pointer machine, is almost tight. We also show how to achieveO(logn) query time at the expense ofO(n ^d+?) storage for any fixed ? > 0. To fine-tune our results in the reporting case we also establish new zone theorems for arrangements and merged arrangements of planes in 3-space, which are of independent interest.     

Towards optimal range medians

We consider the following problem: Given an unsorted array of n elements, and a sequence of intervals in the array, compute the median in each of the subarrays defined by the intervals. We describe a simple algorithm which needs O(nlogk+klogn) time to answer k such median queries. This improves previous algorithms by a logarithmic factor and matches a comparison lower bound for k=O(n). The space complexity of our simple algorithm is O(nlogn) in the pointer machine model, and O(n) in the RAM model. In the latter model, a more involved O(n) space data structure can be constructed in O(nlogn) time where the time per query is reduced to O(logn/loglogn). We also give efficient dynamic variants of both data structures, achieving O(log²n) query time using O(nlogn) space in the comparison model and O((logn/loglogn)²) query time using O(nlogn/loglogn) space in the RAM model, and show that in the cell-probe model, any data structure which supports updates in O(log^O(1)n) time must have Ω(logn/loglogn) query time.Our approach naturally generalizes to higher-dimensional range median problems, where element positions and query ranges are multidimensional—it reduces a range median query to a logarithmic number of range counting queries.     

数据仓库系统中层次式Cube存储结构

区域查询是数据仓库上支持联机分析处理(on-line analytical processing,简称OLAP)的重要操作.近几年,人们提出了一些支持区域查询和数据更新的Cube存储结构.然而这些存储结构的空间复杂性和时间复杂性都很高,难以在实际中使用.为此,提出了一种层次式Cube存储结构HDC(hierarchical data cube)及其上的相关算法.HDC上区域查询的代价和数据更新代价均为O(log^dn),综合性能为O((logn)^2d)(使用C_qC_u模型)或O(K(logn)^d)(使用C_qn_q+C_un_u模型).理论分析与实验表明,HDC的区域查询代价、数据更新代价、空间代价以及综合性能都优于目前所有的Cube存储结构.     

Fully dynamic biconnectivity in graphs

We present an algorithm for maintaining the biconnected components of a graph during a sequence of edge insertions and deletions. It requires linear storage and preprocessing time. The amortized running time for insertions and for deletions isO(m ^2/3 ), wherem is the number of edges in the graph. Any query of the form ‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the first sublinear algorithm for this problem. We can also output all articulation points separating any two vertices efficiently. If the input is a plane graph, the amortized running time for insertions and deletions drops toO(√n logn) and the query time isO(log² n), wheren is the number of vertices in the graph. The best previously known solution takes timeO(n ^2/3 ) per update or query.     

The single facility location problem with minimum distance constraints

We consider the problem of locating a single facility (server) in the plane, where the location of the facility is restricted to be outside a specified forbidden region (neighborhood) around each demand point. Two models are discussed. In the restricted 1-median model, the objective is to minimize the sum of the weighted rectilinear distances from the n customers to the facility. We present an O(n log n) algorithm for this model, improving upon the O(n³) complexity bound of the algorithm by Brimberg and Wesolowsky (1995). In the restricted 1-center model the objective is to minimize the maximum of the weighted rectilinear distances between the customers and the serving facility. We present an O(n log n) algorithm for finding an optimal 1-center. We also discuss some related models, involving the Euclidean norm.     

Path-matching problems

The notion of matching in graphs is generalized in this paper to a set of paths rather than to a set of edges. The generalized problem, which we call thepath-matching problem, is to pair the vertices of an undirected weighted graph such that the paths connecting each pair are subject to certain objectives and/or constraints. This paper concentrates on the case where the paths are required to be edge-disjoint and the objective is to minimize the maximal cost of a path in the matching (i.e., the bottleneck version). Other variations of the problem are also mentioned. Two algorithms are presented to find the best matching under the constraints listed above for trees. Their worst-case running times areO(n logd logw), whered is the maximal degree of a vertex,w is the maximal cost of an edge, andn is the size of the tree, andO(n ²), respectively. The problem is shown to be NP-complete for general graphs. Applications of these problems are also discussed.     

Triangulating input-constrained planar point sets

We present a linear-time algorithm for computing a triangulation of n points in 2D whose positions are constrained to n disjoint disks of uniform size, after O(nlogn) preprocessing applied to these disks. Our algorithm can be extended to any collection of convex sets of bounded areas and aspect ratios, assuming no point lies in more than some constant number of sets (bounded depth of overlap), and each set contains only a constant number of query points.     

Succinct 2D Dictionary Matching

The dictionary matching problem seeks all locations in a given text that match any of the patterns in a given dictionary. Efficient algorithms for dictionary matching scan the text once, searching for all patterns simultaneously. Existing algorithms that solve the 2-dimensional dictionary matching problem all require working space proportional to the size of the dictionary. This paper presents the first efficient 2-dimensional dictionary matching algorithm that operates in small space. Given d patterns, D={P ₁,…,P _d }, each of size m×m, and a text T of size n×n, our algorithm finds all occurrences of P _i , 1≤i≤d, in T. The preprocessing of the dictionary forms a compressed self-index of the patterns, after which the original dictionary may be discarded. Our algorithm uses O(dmlogdm) extra bits of space. The time complexity of our algorithm is close to linear, O(dm ²+n ² τlogσ), where τ is the time it takes to access a character in the compressed self-index and σ is the size of the alphabet. Using recent results τ is at most sub-logarithmic.     

A bucketing algorithm for the orthogonal segment intersection search problem and its practical efficiency

The orthogonal segment intersection search problem is stated as follows: given a setS ofn orthogonal segments in the plane, report all the segments ofS that intersect a given orthogonal query segment. For this problem, we propose a simple and practical algorithm based on bucketing techniques. It constructs, inO(n) time preprocessing, a search structure of sizeO(n) so that all the segments ofS intersecting a query segment can be reported inO(k) time in the average case, wherek is the number of the reported segments. The proposed algorithm as well as existing algorithms is implemented in FORTRAN, and their practical efficiencies are investigated through computational experiments. It is shown that ourO(k) search time,O(n) space, andO(n) preprocessing time algorithm is in practice the most efficient among the algorithms tested.     

The longest common subsequence problem revisited

This paper re-examines, in a unified framework, two classic approaches to the problem of finding a longest common subsequence (LCS) of two strings, and proposes faster implementations for both. Letl be the length of an LCS between two strings of lengthm andn ≥m, respectively, and let s be the alphabet size. The first revised strategy follows the paradigm of a previousO(ln) time algorithm by Hirschberg. The new version can be implemented in timeO(lm · min logs, logm, log(2n/m)), which is profitable when the input strings differ considerably in size (a looser bound for both versions isO(mn)). The second strategy improves on the Hunt-Szymanski algorithm. This latter takes timeO((r +n) logn), wherer≤mn is the total number of matches between the two input strings. Such a performance is quite good (O(n logn)) whenr～n, but it degrades to Θ(mn logn) in the worst case. On the other hand the variation presented here is never worse than linear-time in the productmn. The exact time bound derived for this second algorithm isO(m logn +d log(2mn/d)), whered ≤r is the number ofdominant matches (elsewhere referred to asminimal candidates) between the two strings. Both algorithms require anO(n logs) preprocessing that is nearly standard for the LCS problem, and they make use of simple and handy auxiliary data structures.     

Internal and external algorithms for the points-in-regions problem—the inside join of geo-relational algebra

We consider the problem of collectively locating a set of points within a set of disjoint polygonal regions when neither for points nor for regions preprocessing is allowed. This problem arises in geometric database systems. More specifically it is equivalent to computing theinside join of geo-relational algebra, a conceptual model for geo-data management. We describe efficient algorithms for solving this problem based on plane-sweep and divide-and-conquer, requiringO(n(logn) +t) andO(n(log² n) +t) time, respectively, andO(n) space, wheren is the total number of points and edges, and (is the number of reported (point, region) pairs. Since the algorithms are meant to be practically useful we consider as well as the internal versions-running completely in main memory-versions that run internally but use much less than linear space and versions that run externally, that is, require only a constant amount of internal memory regardless of the amount of data to be processed. Comparing plane-sweep and divide-and-conquer, it turns out that divide-and-conquer can be expected to perform much better in the external case even though it has a higher internal asymptotic worst-case complexity. An interesting theoretical by-product is a new general technique for handling arbitrarily large sets of objects clustered on a singlex-coordinate within a planar divide-and-conquer algorithm and a proof that the resulting “unbalanced” dividing does not lead to a more than logarithmic height of the tree of recursive calls.     

Improved Constructions for Non-adaptive Threshold Group Testing

The basic goal in combinatorial group testing is to identify a set of up to d defective items within a large population of size n?d using a pooling strategy. Namely, the items can be grouped together in pools, and a single measurement would reveal whether there are one or more defectives in the pool. The threshold model is a generalization of this idea where a measurement returns positive if the number of defectives in the pool reaches a fixed threshold u>0, negative if this number is no more than a fixed lower threshold ?<u, and may behave arbitrarily otherwise. We study non-adaptive threshold group testing (in a possibly noisy setting) and show that, for this problem, O(d ^g+2(logd)log(n/d)) measurements (where g:=u???1 and u is any fixed constant) suffice to identify the defectives, and also present almost matching lower bounds. This significantly improves the previously known (non-constructive) upper bound O(d ^u+1log(n/d)). Moreover, we obtain a framework for explicit construction of measurement schemes using lossless condensers. The number of measurements resulting from this scheme is ideally bounded by O(d ^g+3(logd)logn). Using state-of-the-art constructions of lossless condensers, however, we obtain explicit testing schemes with O(d ^g+3(logd)quasipoly(logn)) and O(d ^g+3+β poly(logn)) measurements, for arbitrary constant β>0.     

Parallel algorithms for shortest path problems in polygons

Given ann-vertex simple polygon we address the following problems: (i) find the shortest path between two pointss andd insideP, and (ii) compute the shortestpath tree between a single points and each vertex ofP (which implicitly represents all the shortest paths). We show how to solve the first problem inO(logn) time usingO(n) processors, and the more general second problem inO(log² n) time usingO(n) processors, and the more general second problem inO(log² n) time usingO(n) processors for any simple polygonP. We assume the CREW RAM shared memory model of computation in which concurrent reads are allowed, but no two processors should attempt to simultaneously write in the same memory location. The algorithms are based on the divide-and-conquer paradigm and are quite different from the known sequential algorithmsResearch supported by the Faculty of Graduate Studies and Research (McGill University) grant 276-07     

PRAM和LARPBS模型上有向序列翻转距离并行算法

分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n²)处理器,时间复杂度为O(log²n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n³)处理器,计算时间复杂度为O(logn).     

Chromatic distribution of k-nearest neighbors of a line segment in a planar colored point set

Let P be a set of n colored points distributed arbitrarily in R². The chromatic distribution of the k-nearest neighbors of a query line segment ? is to report the number of points of each color among the k-nearest points of the query line segment. While solving this problem, we have encountered another interesting problem, namely the semicircular range counting query. Here a set of n points is given. The objective is to report the number of points inside a given semicircular range. We propose a simple algorithm for this problem with preprocessing time and space complexity O(n³), and the query time complexity O(logn). Finally, we propose the algorithm for reporting the chromatic distribution of k nearest neighbors of a query line segment. Using our proposed technique for semicircular range counting query, it runs in O(log²n) time.     

Robust gossiping with an application to consensus

We study deterministic gossiping in synchronous systems with dynamic crash failures. Each processor is initialized with an input value called rumor. In the standard gossip problem, the goal of every processor is to learn all the rumors. When processors may crash, then this goal needs to be revised, since it is possible, at a point in an execution, that certain rumors are known only to processors that have already crashed. We define gossiping to be completed, for a system with crashes, when every processor knows either the rumor of processor v or that v has already crashed, for any processor v. We design gossiping algorithms that are efficient with respect to both time and communication. Let t<n be the number of failures, where n is the number of processors. If , then one of our algorithms completes gossiping in O(log²t) time and with O(npolylogn) messages. We develop an algorithm that performs gossiping with O(n^1.77) messages and in O(log²n) time, in any execution in which at least one processor remains non-faulty. We show a trade-off between time and communication in gossiping algorithms: if the number of messages is at most O(npolylogn), then the time has to be at least . By way of application, we show that if n−t=Ω(n), then consensus can be solved in O(t) time and with O(nlog²t) messages.     

A Parallel Algorithm for Computing Polygon Set Operations

We present a parallel algorithm for performing boolean set operations on generalized polygons that have holes in them. The intersection algorithm has a processor complexity of O(m²n²) processors and a time complexity of O(max(2log m, log²n)), where m is the maximum number of vertices in any loop of a polygon, and n is the maximum number of loops per polygon. The union and difference algorithms have a processor complexity of O(m²n²) and time complexity of O(log m) and O(2log m, log n) respectively. The algorithm is based on the EREW PRAM model. The algorithm tries to minimize the intersection point computations by intersecting only a subset of loops of the polygons, taking advantage of the topological structure of the two polygons. We believe this will result in better performance on the average as compared to the worst case. Though all the algorithms presented here are deterministic, randomized algorithms such as sample sort can be used for the sorting subcomponent of the algorithms to obtain fast practical implementations.     

Spin-the-Bottle Sort and Annealing Sort: Oblivious Sorting via Round-Robin Random Comparisons

We study sorting algorithms based on randomized round-robin comparisons. Specifically, we study Spin-the-bottle sort, where comparisons are unrestricted, and Annealing sort, where comparisons are restricted to a distance bounded by a temperature parameter. Both algorithms are simple, randomized, data-oblivious sorting algorithms, which are useful in privacy-preserving computations, but, as we show, Annealing sort is much more efficient. We show that there is an input permutation that causes Spin-the-bottle sort to require Ω(n ²logn) expected time in order to succeed, and that in O(n ²logn) time this algorithm succeeds with high probability for any input. We also show there is a specification of Annealing sort that runs in O(nlogn) time and succeeds with very high probability.     

New Algorithms for Facility Location Problems on the Real Line

In this paper, we study the facility location problems on the real line. Given a set of n customers on the real line, each customer having a cost for setting up a facility at its position, and an integer k, we seek to find at most k of the customers to set up facilities for serving all n customers such that the total cost for facility set-up and service transportation is minimized. We consider several problem variations including the k-median, the k-coverage, and the linear model. The previously best algorithms for these problems all take O(nk) time. Our new algorithms break the O(nk) time bottleneck and solve these problems in sub-quadratic time. Our algorithms are based on a new problem modeling and interesting algorithmic techniques, which may find other applications as well.