Finding the intersection of n half-spaces in time O(nlogn)

Given a set of n half-spaces in three dimensional space, we develop an algorithm for finding their common intersection in time O(n log n). The intersection, if nonempty, is presented as a convex polyhedron. The algorithm is summarized as follows: (i) the half-spaces are placed in two sets depending upon whether they contain or do not contain the origin; (ii) the half-spaces in each of these sets are dualized to points, and the convex hulls of the dualized sets are obtained in time O(n log n); (iii) since the half-space intersection is nonempty if and only if these two convex hulls are disjoint, a separating plane is found, also in time O(n log n); (iv) after applying a linear spatial transformation which maps the separating plane to infinity, the convex hull of the union of the two transformed convex hulls is the transformed intersection of the half-spaces. Since the letter can be found in time O(n), the overall running time of the procedure is O(n log n). A significant consequence of this result is that a three-variable linear, or convex, programming problem can be asymptotically solved faster than by the Simplex algorithm, in the worst case.     

具有O(n)时间复杂度的分布式请求集生成算法

在大规模完全分布式系统的互斥问题上,快速生成请求集是必要的。在基于松弛差集的相关原理上,引入了二次松弛差集的概念。经分析相关概念及定理,将原本“求差”的过程变为“求和”的过程;进而利用 “求和”步骤间的递推关系,大大减少了求和步骤,使整个算法的时间复杂度控制在O(n)。与时间复杂度同为O(n^2)的其他经典算法相比,生成的请求集长度仍保持在2n^(1/2)的数量级。     

A balanced search tree with O(1) worst-case update time

Summary In this paper a new data structure is described for performing member and neighbor queries in O(logn) time that allows for O(1) worst-case update time once the position of the inserted or deleted element is known. In this way previous solutions that achieved only O(1) amortized time or O(log^* n) worst-case time are improved. The method is based on a combinatorial result on the height of piles that are split after some fixed number of insertions. This combinatorial result is interesting in its own right and might have other applications as well.     

Sorting Stably,in Place,with O(n log n) Comparisons and O(n) Moves

We settle a long-standing open question, namely whether it is possible to sort a sequence of n elements stably (i.e., preserving the original relative order of the equal elements), using O(1) auxiliary space and performing O(n log n) comparisons and O(n) data moves. Munro and Raman stated this problem in J. Algorithms (13, 1992) and gave an in-place but unstable sorting algorithm that performs O(n) data moves and O(n^1+ε) comparisons. Subsequently (Algorithmica, 16, 1996) they presented a stable algorithm with these same bounds. Recently, Franceschini and Geffert (FOCS 2003) presented an unstable sorting algorithm that matches the asymptotic lower bounds on all computational resources.     

查找、插入及删除时间为O(1)的方法研究

提出一种查找、插入及删除对象时间为O(1)的方法,以双向链表存储数据对象,通过地址指针方式获取对象.即客户端与服务器进行数据的交互时,传输中包含对象在服务器的地址指针值,服务器根据地址指针值,直接获取对象信息的方式.同时提出了计算指针值的校验和的算法,解决验证地址的有效性问题和安全问题,及提出了细粒度锁对象方式解决并发访问的问题.     

Stable unmerging in linear time and constant space

In the Summer 1985 issue of SIGACT News, Santoro enquired about the space-time complexity of unmerging. Suppose that two sorted lists A and B of total size n are merged to produce the list L. The problem is to separate L into A and B in sorted order. An optimal algorithm is presented which unmerges in O(n) time using O(1) extra space, and which is stable.     

Insertion Sort is O(n log n)

Traditional Insertion Sort runs in O(n²) time because each insertion takes O(n) time. When people run Insertion Sort in the physical world, they leave gaps between items to accelerate insertions. Gaps help in computers as well. This paper shows that Gapped Insertion Sort has insertion times of O(log n) with high probability, yielding a total running time of O(n log n) with high probability.     

Improving time and space efficiency in generalized binary search trees

Summary This paper deals with main memory data structures for which time and space performance are simultaneously considered. The main contribution is a new data structure called Generalised Binary Search Tree (GBS-tree) together with searching and updating algorithms on this structure. GBS-trees generalise different data structures based on binary trees that have appeared in the literature. A k-t GBS-tree allows up to t keys per node and subtrees in the tree's fringe of exactly 2k-1 full nodes are kept balanced. Their time and space performances are analysed in depth. The time performance is expressed in terms of the average and the variance of the number of binary comparisons between a given key and keys already in the structure. The space performance measures both the space used to space generated ratio (space utilization factor) and the pointers to keys ratio of these trees. The analysis shows that the time performance always improves when GBS-trees of higher order are considered. In the absence of balancing techniques, larger values of t, which produces smaller pointers to key ratios, induce unacceptably poor space utilizations factors. We show that both pointers to keys ratio and space utilization factor improve when larger values of k are used. Thus, local balancing techniques are adequate, not only for time performance improvement, but also, for space performance improvement.     

An O(n) algorithm for the linear multiple choice knapsack problem and related problems

We present an O(n) algorithm for the Linear Multiple Choice Knapsack Problem and its d-dimensional generalization which is based on Megiddo's (1982) algorithm for linear programming. We also consider a certain type of convex programming problems which are common in geometric location models. An application of the linear case is an O(n) algorithm for finding a least distance hyperplane in R^d according to the rectilinear norm. The best previously available algorithm for this problem was an O(n log²n) algorithm for the two-dimensional case. A simple application of the nonlinear case is an O(n) algorithm for finding the point at which a ‘pursuer’ minimizes its distance from the furthest among n ‘targets’, when the trajectories involved are straight lines in R^d.     

Voronoi-based range and continuous range query processing in mobile databases

With the wide availability of mobile devices (smart phones, iPhones, etc.), mobile location-based queries are increasingly in demand. One of the most frequent queries is range search which returns objects of interest within a pre-defined area. Most of the existing methods are based on the road network expansion method – expanding all nodes (intersections and objects) and computing the distance of each node to the query point. Since road networks are extremely complex, node expansion approaches are inefficient. In this paper, we propose a method, Voronoi Range Search (VRS) based on the Voronoi diagram, to process range search queries efficiently and accurately by partitioning the road networks to some special polygons. Then we further propose Voronoi Continuous Range (VCR) to satisfy the requirement for continuous range search queries (moving queries) based on VRS. Our empirical experiments show that VRS and VCR surpass all their rivals for both static and moving queries.     

Fully dynamic distributed search trees can be balanced in O(lg2N) time

In this paper we consider the dictionary problem in a message-passing distributed environment. We introduce a new version, based on AVL-trees, of distributed search trees, the first to be fully scalable, that is, able to both grow and shrink as long as keys are inserted and deleted. We prove that in the worst case a key can be inserted, searched, or deleted with $\text{O(}\text{lg}{}^2\text{N)}$ messages. We show that for the introduced distributed search tree this bound is tight. Since the defined structure maintains the relative order of the keys, it can also support queries that refer to the linear order of keys, such as nearest neighbor or range queries.     

O(n) routing in rearrangeable networks

In (2n−1)-stage rearrangeable networks, the routing time for any arbitrary permutation is Ω(n²) compared to its propagation delay O(n) only. Here, we attempt to identify the sets of permutations, which are routable in O(n) time in these networks. We define four classes of self-routable permutations for Benes network. An O(n) algorithm is presented here, that identifies if any permutation P belongs to one of the proposed self-routable classes, and if yes, it also generates the necessary control vectors for routing P. Therefore, the identification, as well as the switch setting, both problems are resolved in O(n) time by this algorithm. It covers all the permutations that are self-routable by anyone of the proposed techniques. Some interesting relationships are also explored among these four classes of permutations, by applying the concept of ‘group-transformations’ [N. Das, B.B. Bhattacharya, J. Dattagupta, Hierarchical classification of permutation classes in multistage interconnection networks, IEEE Trans. Comput. (1993) 665–677] on these permutations. The concepts developed here for Benes network, can easily be extended to a class of (2n−1)-stage networks, which are topologically equivalent to Benes network. As a result, the set of permutations routable in a (2n−1)-stage rearrangeable network, in a time comparable to its propagation delay has been extended to a large extent.     

Sorting numbers in linear expected time and optimal extra space

An algorithm is shown that sorts n numbers, each representable in h bits, in θ(n) time on the average where the numbers to be sorted are selected randomly from some interval. The algorithm only uses θ(log n) bits of extra space, which is asymptotically optimal.     

Range mode and range median queries in constant time and sub-quadratic space

Given a list of n items and a function defined over sub-lists, we study the space required for computing the function for arbitrary sub-lists in constant time.For the function mode we improve the previously known space bound O(n²/logn) to O(n²loglogn/log²n) words.For median the space bound is improved to O(n²loglog²n/log²n) words from O(n²⋅log(k)n/logn), where k is an arbitrary constant and log(k) is the iterated logarithm.     

无线广播环境下的空间范围查询处理

为实现无线广播环境下快速且低能耗的空间范围查询,提出了一种基于网格空间索引的范围查询处理算法(RQGSI)。该算法在服务器端对空间数据对象建立网格空间索引以缩短调谐时间,并按Hilbert曲线填充顺序对划分后的网格进行调度以优化访问时间;在客户端设计了查询处理算法对数据对象进行过滤和剪枝;最后,通过模拟实验验证了RQGSI算法的性能。实验结果表明,RQGSI算法比基于R树的索引(RI)算法在调谐时间上降低约10%,在访问时间上降低约8%,RQGSI算法可以实现更快且更低能耗的范围查询。     

Efficient trajectory compression and range query processing

World Wide Web - Nowadays, there are ubiquitousness of GPS sensors in various devices collecting, transmitting and storing tremendous trajectory data. However, such an unprecedented scale of GPS...