Cache-Oblivious Range Reporting with Optimal Queries Requires Superlinear Space

We consider a number of range reporting problems in two and three dimensions and prove lower bounds on the amount of space used by any cache-oblivious data structure for these problems that achieves the optimal query bound of O(log  _B N+K/B) block transfers, where K is the size of the query output.     

The dimension of suborders of the Boolean lattice

We consider the order dimension of suborders of the Boolean latticeB _n . In particular we show that the suborder consisting of the middle two levels ofB _n dimension at most of 6 log₃ n. More generally, we show that the suborder consisting of levelss ands+k ofB _n has dimensionO(k ² logn).The research of the second author was supported by Office of Naval Research Grant N00014-90-J-1206.The research of the third author was supported by Grant 93-011-1486 of the Russian Fundamental Research Foundation.     

Sums and differences of four kth powers

We prove an upper bound for the number of representations of a positive integer N as the sum of four kth powers of integers of size at most B, using a new version of the determinant method developed by Heath-Brown, along with recent results by Salberger on the density of integral points on affine surfaces. More generally we consider representations by any integral diagonal form. The upper bound has the form O_N(B^c/?k){O_{N}(B^{c/\sqrt{k}})}, whereas earlier versions of the determinant method would produce an exponent for B of order k ^−1/3 (uniformly in N) in this case. Furthermore, we prove that the number of representations of a positive integer N as a sum of four kth powers of non-negative integers is at most O_e(N^1/k+2/k3/2+e){O_{\varepsilon}(N^{1/k+2/k^{3/2}+\varepsilon})} for k ≥ 3, improving upon bounds by Wisdom.     

ISB-tree: A new indexing scheme with efficient expected behaviour

We present the interpolation search B-tree (ISB-tree), a new cache-aware indexing scheme that supports update operations (insertions and deletions) in $O(1)$ worst-case block transfers and search operations in $O({\log }_B\log n)$ expected block transfers, where B represents the disk block size and n denotes the number of stored elements. The expected search bound holds with high probability for a large class of (unknown) input distributions. The worst-case search bound of our indexing scheme is $O({\log }_{B}n)$ block transfers. Our update and expected search bounds constitute a considerable improvement over the $O({\log }_{B}n)$ worst-case block transfer bounds for search and update operations achieved by the B-tree and its numerous variants. This is also verified by an accompanying experimental study.     

On Computing the Subset Graph of a Collection of Sets

Let a given collection of sets have size N measured by the sum of the cardinalities. Yellin and Jutla presented an algorithm which constructed the partial order induced by the subset relation (a “subset graph”) in a claimed O(N²/log N) operations over a dictionary ADT, and exhibited a collection whose subset graph had Θ(N²/log² N) edges. This paper first establishes a matching upper bound on the number of edges in a subset graph. It also presents a finer analysis of the algorithm, which confirms the claimed upper bound and shows it to be tight. A simple implementation requiring O(1) bit-parallel operations per ADT operation is presented, along with a variant of the algorithm with an implementation requiring O(N²/log N) RAM operations.     

Finding thek smallest spanning trees

We give improved solutions for the problem of generating thek smallest spanning trees in a graph and in the plane. Our algorithm for general graphs takes timeO(m log(m, n)=k ²); for planar graphs this bound can be improved toO(n+k ²). We also show that thek best spanning trees for a set of points in the plane can be computed in timeO(min(k ² n+n logn,k ²+kn log(n/k))). Thek best orthogonal spanning trees in the plane can be found in timeO(n logn+kn log log(n/k)+k ²).     

On Shellsort and the frobenius problem

A boundO(N ^1+1/k ) for the running time of Shellsort, withO(logN) passes, is proved very simply by application of a Frobenius basis withk elements.     

A faster polynomial algorithm for the unbalanced Hitchcock transportation problem

We present a new algorithm for the Hitchcock transportation problem. On instances with n sources and k sinks, our algorithm has a worst-case running time of O(nk²(logn+klogk)). It closes a gap between algorithms with running time linear in n but exponential in k and a polynomial-time algorithm with running time O(nk²log²n).     

Euclidean minimum spanning trees and bichromatic closest pairs

We present an algorithm to compute a Euclidean minimum spanning tree of a given setS ofN points inE ^d in timeO(F _d (N,N) log ^d N), whereF _d (n,m) is the time required to compute a bichromatic closest pair amongn red andm green points inE ^d . IfF _d (N,N)=Ω(N ^1+ε), for some fixed ɛ>0, then the running time improves toO(F _d (N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected timeO((nm logn logm)^2/3+m log² n+n log² m) inE ₃, which yields anO(N ^4/3 log^4/3 N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE ³. Ind≥4 dimensions we obtain expected timeO((nm)^{1−1/([d/2]+1)+ε}+m logn+n logm) for the bichromatic closest pair problem andO(N ^{2−2/([d/2]+1)ε}) for the Euclidean minimum spanning tree problem, for any positive ɛ. The first, second, and fourth authors acknowledge support from the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center under NSF Grant STC 88-09648. The second author's work was supported by the National Science Foundation under Grant CCR-8714565. The third author's work was supported by the Deutsche Forschungsgemeinschaft under Grant A1 253/1-3, Schwerpunktprogramm “Datenstrukturen und effiziente Algorithmen”. The last two authors' work was also partially supported by the ESPRIT II Basic Research Action of the EC under Contract No. 3075 (project ALCOM).     

Maintaining the minimal distance of a point set in polylogarithmic time

A dynamic data structure is given that maintains the minimal distance in a set ofn points ink-dimensional space inO((logn) ^k log logn) amortized time per update. The size of the data structure is bounded byO(n(logn) ^k ). Distances are measured in the MinkowskiL _t -metric, where 1 t . This is the first dynamic data structure that maintains the minimal distance in polylogarithmic time for fully on-line updates.This work was supported by the ESPRIT II Basic Research Actions Program, under Contract No. 3075 (project ALCOM).     

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, theFibonacci heap (or F-heap) supports arbitrary deletion inO(logn) amortized time and other heap operations inO(1) amortized time. In this paper we use F-heaps to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. For an undirected graph containingn vertices andm edges, our minimum spanning tree algorithm runs inO(m logβ (m, n)) time, improved fromO(mβ(m, n)) time, whereβ(m, n)=min {i|log⁽ⁱ⁾ n ≦m/n}. Our minimum spanning tree algorithm for directed graphs runs inO(n logn + m) time, improved fromO(n log n +m log log log_(m/n+2) n). Both algorithms can be extended to allow a degree constraint at one vertex. Research supported in part by National Science Foundation Grant MCS-8302648. Research supported in part by National Science Foundation Grant MCS-8303139. Research supported in part by National Science Foundation Grant MCS-8300984 and a United States Army Research Office Program Fellowship, DAAG29-83-GO020.     

Variable-priority queue and doughnut routing

This paper proposes a new data structure called a variable-priority queue. The queue supports, in addition to the ordinary queue operations, an operation MIN to find an item of minimum key and three operations to change keys of items. Any sequence of these m operations can be processed in O(m) time. Furthermore, as its application, this paper presents two efficient algorithms for network problems. The first finds multicommodity flows in cycles in linear time. The second, using the first, finds edge-disjoint paths connecting terminal pairs in a doughnut-shaped grid. The grid is bounded by two nested rectangles, and terminals are specified on the two rectangular boundaries outside the four corners. If there are k terminal pairs and all the terminals are ordered in clockwise order around rectangles, then the algorithm decides in O(k) time whether there are edge-disjoint paths connecting terminals in the grid, and actually finds edge-disjoint paths in O(k log k) time.     

On the evaluation of the Eigenvalues of a banded toeplitz block matrix

Let A = (a_ij) be an n × n Toeplitz matrix with bandwidth k + 1, K = r + s, that is, a_ij = a_j−i, i, J = 1,… ,n, a_i = 0 if i > s and if i < -r. We compute p(λ)= det(A - λI), as well as p(λ)/p′(λ), where p′(λ) is the first derivative of p(λ), by using O(k log k log n) arithmetic operations. Moreover, if a_i are m × m matrices, so that A is a banded Toeplitz block matrix, then we compute p(λ), as well as p(λ)/p′(λ), by using O(m³k(log² k + log n) + m²k log k log n) arithmetic operations. The algorithms can be extended to the computation of det(A − λB) and of its first derivative, where both A and B are banded Toeplitz matrices. The algorithms may be used as a basis for iterative solution of the eigenvalue problem for the matrix A and of the generalized eigenvalue problem for A and B.     

Intersection queries in sets of disks

In this paper we develop some new data structures for storing a set of disks that can answer different types of intersection queries efficiency. If the disks are non-intersecting we obtain a linear size data structure that can report allk disks intersecting a query line segment in timeO(n ⁺ +k), wheren is the number of disks,=log₂(1+5)–1 0.695, and is an arbitrarily small positive constant. If the segment is a full line, the query time becomesO(n +k). For intersecting disks we obtain anO(n logn) size data structure that can answer an intersection query in timeO(n ^2/3 log² n+k). We also present a linear size data structure for ray shooting queries, whose query time isO(n ).The research of the first two authors was supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). The work of the third author was supported byDimacs (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center — NSF-STC88-09648.     

Discrepancy in generalized arithmetic progressions

Estimating the discrepancy of the set of all arithmetic progressions in the first N natural numbers was one of the famous open problems in combinatorial discrepancy theory for a long time, successfully solved by K. Roth (lower bound) and Beck (upper bound). They proved that D(N)=min_χmax_A|∑_xAχ(x)|=Θ(N^1/4), where the minimum is taken over all colorings χ:[N]→{−1,1} and the maximum over all arithmetic progressions in [N]={0,…,N−1}.Sumsets of k arithmetic progressions, A₁++A_k, are called k-arithmetic progressions and they are important objects in additive combinatorics. We define D_k(N) as the discrepancy of the set {P∩[N]:P is a k-arithmetic progression}. The second author proved that D_k(N)=Ω(N^k/(2k+2)) and Přívětivý improved it to Ω(N^1/2) for all k≥3. Since the probabilistic argument gives D_k(N)=O((NlogN)^1/2) for all fixed k, the case k=2 remained the only case with a large gap between the known upper and lower bounds. We bridge this gap (up to a logarithmic factor) by proving that D_k(N)=Ω(N^1/2) for all k≥2.Indeed we prove the multicolor version of this result.     

A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs

1.IntroductionLetG=(V,E,W)beaconnected,weightedandundirectedgraph,VeEE,w(e)(相似文献   

A fast line-sweep algorithm for hidden line elimination

Fast hidden line elimination algorithms can be obtained by minor modifications to algorithms developed for reporting intersections of polygons. We show how the same modifications which have been applied to segment trees can be applied to the data structure of Swart and Ladner as well, leading to anO((n+k)logn) time hidden line elimination algorithm (n is the number of boundary edges of the input polygons andk is the number of intersections of the edges on the projection plane). The algorithm improves the fastest previous line-sweep algorithm for the problem by a factorO(logn).This work was supported by the grant Ot 64/4-2 from the Deutsche Forschungsgemeinschaft.On leave from the Department of Computer Science, University of Helsinki, Finland.     

Rectilinear line segment intersection,layered segment trees,and dynamization

The aim of the present paper is to provide an efficient solution to the following problem: “Given a family of n rectilinear line segments in two-space report all intersections in the family with a query consisting of an arbitrary rectilinear line segment.” We provide an algorithm which takes O(nlog₂n) preprocessing time, o(nlog₂n) space and O(log₂n + k) query time, where k is the number of reported intersections. This solution serves to introduce a powerful new data structure, the layered segment tree, which is of independent interest. Second it yields, by way of recent dynamization techniques, a solution to the on-line version of the above problem, that is the operations INSERT and DELETE and QUERY with a line segment are allowed. Third it also yields a new nonscanning solution to the batched version of the above problem. Finally we apply these techniques to the problem obtained by replacing “line segment” by “rectangle” in the above problem, giving an efficient solution in this case also.     

Torus quotients of homogeneous spaces of the general linear group and the standard representation of certain symmetric groups

We give a stratification of the GIT quotient of the Grassmannian G _2,n modulo the normaliser of a maximal torus of SL _n (k) with respect to the ample generator of the Picard group of G _2,n . We also prove that the flag variety GL _n (k)/B _n can be obtained as a GIT quotient of GL _n+1(k)/B _n+1 modulo a maximal torus of SL _n+1(k) for a suitable choice of an ample line bundle on GL _n+1(k)/B _n+1. Dedicated to Professor C De Concini on the occasion of his 60th birthday     

A new duality result concerning voronoi diagrams

A new duality between order-k Voronoi diagrams inE ^d and convex hulls inE ^d+1 is established. It implies a reasonably simple algorithm for computing the order-k diagram forn points in the plane inO(k ² n logn) time and optimalO(k(n–k)) space.Research was supported by the Austrian Fond zur Foerderung der wissenschaftlichen Forschung.