共查询到20条相似文献,搜索用时 31 毫秒
1.
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. 相似文献
2.
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 log3
n. More generally, we show that the suborder consisting of levelss ands+k ofB
n
has dimensionO(k
2 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. 相似文献
3.
Oscar Marmon 《Monatshefte für Mathematik》2011,53(9):55-74
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 ON(Bc/?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 Oe(N1/k+2/k3/2+e){O_{\varepsilon}(N^{1/k+2/k^{3/2}+\varepsilon})} for k ≥ 3, improving upon bounds by Wisdom. 相似文献
4.
Alexis Kaporis Christos Makris George Mavritsakis Spyros Sioutas Athanasios Tsakalidis Kostas Tsichlas Christos Zaroliagis 《Journal of Discrete Algorithms》2010,8(4):373-387
We present the interpolation search B-tree (ISB-tree), a new cache-aware indexing scheme that supports update operations (insertions and deletions) in worst-case block transfers and search operations in 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 block transfers. Our update and expected search bounds constitute a considerable improvement over the 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. 相似文献
5.
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(N2/log N) operations over a dictionary ADT, and exhibited a collection whose subset graph had Θ(N2/log2 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(N2/log N) RAM operations. 相似文献
6.
David Eppstein 《BIT Numerical Mathematics》1992,32(2):237-248
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
2); for planar graphs this bound can be improved toO(n+k
2). We also show that thek best spanning trees for a set of points in the plane can be computed in timeO(min(k
2
n+n logn,k
2+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
2). 相似文献
7.
Ernst S. Selmer 《BIT Numerical Mathematics》1989,29(1):37-40
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. 相似文献
8.
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(nk2(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(nk2log2n). 相似文献
9.
Pankaj K. Agarwal Herbert Edelsbrunner Otfried Schwarzkopf Emo Welzl 《Discrete and Computational Geometry》1991,6(1):407-422
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 log2
n+n log2
m) inE
3, which yields anO(N
4/3 log4/3
N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE
3. 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). 相似文献
10.
Michiel Smid 《Discrete and Computational Geometry》1992,7(1):415-431
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). 相似文献
11.
Efficient algorithms for finding minimum spanning trees in undirected and directed graphs 总被引:5,自引:0,他引:5
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(i)
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. 相似文献
12.
Hitoshi Suzuki Akira Ishiguro Takao Nishizeki 《Journal of Algorithms in Cognition, Informatics and Logic》1992,13(4)
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. 相似文献
13.
Let A = (aij) be an n × n Toeplitz matrix with bandwidth k + 1, K = r + s, that is, aij = aj−i, i, J = 1,… ,n, ai = 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 ai 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(m3k(log2 k + log n) + m2k 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. 相似文献
14.
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,=log2(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 log2
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. 相似文献
15.
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χmaxA|∑xAχ(x)|=Θ(N1/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, A1++Ak, are called k-arithmetic progressions and they are important objects in additive combinatorics. We define Dk(N) as the discrepancy of the set {P∩[N]:P is a k-arithmetic progression}. The second author proved that Dk(N)=Ω(Nk/(2k+2)) and Přívětivý improved it to Ω(N1/2) for all k≥3. Since the probabilistic argument gives Dk(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 Dk(N)=Ω(N1/2) for all k≥2.Indeed we prove the multicolor version of this result. 相似文献
16.
1.IntroductionLetG=(V,E,W)beaconnected,weightedandundirectedgraph,VeEE,w(e)(相似文献
17.
Otto Nurmi 《BIT Numerical Mathematics》1985,25(3):466-472
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. 相似文献
18.
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(nlog2n) preprocessing time, o(nlog2n) space and O(log2n + 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. 相似文献
19.
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 相似文献
20.
Franz Aurenhammer 《Discrete and Computational Geometry》1990,5(1):243-254
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
2
n logn) time and optimalO(k(n–k)) space.Research was supported by the Austrian Fond zur Foerderung der wissenschaftlichen Forschung. 相似文献