共查询到20条相似文献,搜索用时 31 毫秒
1.
In this paper we study dynamic variants of conjugation trees and related structures that have recently been introduced for performing various types of queries on sets of points and line segments, like half-planar range searching, shooting, intersection queries, etc. For most of these types of queries dynamic structures are obtained with an amortized update time ofO(log2
n) (or less) with only minor increases in query times. As an application of the method we obtain an output-sensitive method for hidden surface removal in a set ofn triangles that runs in timeO(nlogn+n
·
k
) where=log2((1+5)/2) 0.695 andk is the size of the visibility map obtained.Research of the second author was partially supported by the ESPRIT II Basic Research Actions Program of the EC, under contract No. 3075 (project ALCOM). 相似文献
2.
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. 相似文献
3.
Martin Hildebrand 《Journal of Theoretical Probability》2001,14(4):1019-1034
This paper considers lazy random walks supported on a random subset of k elements of a finite group G with order n. If k=a log2
n where a>1 is constant, then most such walks take no more than a multiple of log2
n steps to get close to uniformly distributed on G. If k=log2
n+f(n) where f(n) and f(n)/log2
n0 as n, then most such walks take no more than a multiple of (log2
n) ln(log2
n) steps to get close to uniformly distributed. To get these results, this paper extends techniques of Erdös and Rényi and of Pak. 相似文献
4.
LetG
n
()be the semi-direct product of the symmetric groupS
n
by the Steinberg groupSt
n
()of a ringWe first prove thatG
n
()has a Coxeter-type presentation. The canonical morphism St
n
() GL
n
()extends to a group homo Gn() GL
n
()We next determine the kernel of for n = We also give an expression for the generator of the algebraic K group K
2(Z)of the integers in terms of permutation matrices. 相似文献
5.
Pankaj K. Agarwal 《Discrete and Computational Geometry》1990,5(1):533-573
In this paper we present efficient deterministic algorithms for various problems involving lines or segments in the plane, using the partitioning algorithm described in a companion paper [A3]. These applications include: (i) anO(m
2/3
n
2/3 · log2/3
n · log/3 (m/n)+(m+n) logn) algorithm to compute all incidences betweenm points andn lines, where is a constant <3.33; (ii) anO(m
2/3
n
2/3 · log5/3
n · log/3 (m/n)+(m+n) logn) algorithm to computem faces in an arrangement ofn lines; (iii) anO(n
4/3 log(+2)/3
n) algorithm to count the number of intersections in a set ofn segments; (iv) anO(n
4/3 log( + 2)/3
n) algorithm to count red-blue intersections between two sets of segments, and (v) anO(n
3/2 log/3
n) algorithm to compute spanning trees with low stabbing number for a set ofn points. We also present an algorithm that, given set ofn points in the plane, preprocesses it, in timeO(nm log+1/2
n), into a data structure of sizeO(m) forn lognmn
2, so that the number of points ofS lying inside a query triangle can be computed inO((n/m) log3/2
n) time.Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. A preliminary version of this paper appears in theProceedings of the 5th ACM Symposium on Computational Geometry, 1989, pp. 11–22. 相似文献
6.
This paper deals with the problem of representing the matching independence system in a graph as the intersection of finitely many matroids. After characterizing the graphs for which the matching independence system is the intersection of two matroids, we study the function (G), which is the minimum number of matroids that need to be intersected in order to obtain the set of matchings on a graph G, and examine the maximal value, (n), for graphs with n vertices. We describe an integer programming formulation for deciding whether (G)k. Using combinatorial arguments, we prove that (n)(log logn). On the other hand, we establish that (n)O(logn/ log logn). Finally, we prove that (n)=4 for n=5,,12, and sketch a proof of (n)=5 for n=13,14,15.An earlier version appears as an extended abstract in the Proceedings of COMB01 [5]. Supported by the Gerhard-Hess-Forschungs-Förderpreis (WE 1462) of the German Science Foundation (DFG) awarded to R. Weismantel. 相似文献
7.
Gil Kalai 《Discrete and Computational Geometry》1988,3(1):1-14
Lets(d, n) be the number of triangulations withn labeled vertices ofS
d–1, the (d–1)-dimensional sphere. We extend a construction of Billera and Lee to obtain a large family of triangulated spheres. Our construction shows that logs(d, n)C
1(d)n
[(d–1)/2], while the known upper bound is logs(d, n)C
2(d)n
[d/2] logn.Letc(d, n) be the number of combinatorial types of simpliciald-polytopes withn labeled vertices. (Clearly,c(d, n)s(d, n).) Goodman and Pollack have recently proved the upper bound: logc(d, n)d(d+1)n logn. Combining this upper bound forc(d, n) with our lower bounds fors(d, n), we obtain, for everyd5, that lim
n(c(d, n)/s(d, n))=0. The cased=4 is left open. (Steinitz's fundamental theorem asserts thats(3,n)=c(3,n), for everyn.) We also prove that, for everyb4, lim
d(c(d, d+b)/s(d, d+b))=0. (Mani proved thats(d, d+3)=c(d, d+3), for everyd.)Lets(n) be the number of triangulated spheres withn labeled vertices. We prove that logs(n)=20.69424n(1+o(1)). The same asymptotic formula describes the number of triangulated manifolds withn labeled vertices.Research done, in part, while the author visited the mathematics research center at AT&T Bell Laboratories. 相似文献
8.
We present cost based filtering methods for Knapsack Problems (KPs). Cost based filtering aims at fixing variables with respect to the objective function. It is an important technique when solving complex problems such as Quadratic Knapsack Problems, or KPs with additional constraints (Constrained Knapsack Problems (CKPs)). They evolve, e.g., when Constraint Based Column Generation is applied to appropriate optimization problems. We develop new reduction algorithms for KP. They are used as propagation routines for the CKP with (nlogn) preprocessing time and (n) time per call. This sums up to an amortized time (n) for (logn) incremental calls where the subsequent problems may differ with respect to arbitrary sets of necessarily included and excluded items. 相似文献
9.
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). 相似文献
10.
Herbert Edelsbrunner Leonidas J. Guibas Micha Sharir 《Discrete and Computational Geometry》1990,5(1):161-196
We show that the total number of edges ofm faces of an arrangement ofn lines in the plane isO(m
2/3–
n
2/3+2
+n) for any>0. The proof takes an algorithmic approach, that is, we describe an algorithm for the calculation of thesem faces and derive the upper bound from the analysis of the algorithm. The algorithm uses randomization and its expected time complexity isO(m
2/3–
n
2/3+2
logn+n logn logm). If instead of lines we have an arrangement ofn line segments, then the maximum number of edges ofm faces isO(m
2/3–
n
2/3+2
+n (n) logm) for any>0, where(n) is the functional inverse of Ackermann's function. We give a (randomized) algorithm that produces these faces and takes expected timeO(m
2/3–
n
2/3+2
log+n(n) log2
n logm).The first author is pleased to acknowledge partial support by the Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and the National Science Foundation under Grant CCR-8714565. Work on this paper by the third author has been supported by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation Grant DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD-the Israeli National Council for Research and Development. A preliminary version of this paper has appeared in theProceedings of the 4th ACM Symposium on Computational Geometry, 1988, pp. 44–55. 相似文献
11.
M. Talagrand 《Geometric And Functional Analysis》1993,3(5):502-526
Consider a centered Gaussian measure on a separable Banach spaceX. Denote byK the unit ball of the reproducing kernel of , and consider a symmetric convex setC ofX. We provide two-sided estimates of (C+tK). We determine in a very general setting at which rate for the gauge ofC the variablesY
n
(2 logn)–1/2 cluster toK, when (Y
n
) is an i.i.d. sequence distributed like . The rate depends only on the behavior of the function (C) as 0.Partially supported by an NSF grant 相似文献
12.
A. D. Korshunov 《Mathematical Notes》1971,9(3):155-160
LetG(n) be the set of all nonoriented graphs with n enumerated points without loops or multiple lines, and let vk(G) be the number of mutually nonisomorphic k-point subgraphs of G G(n). It is proved that at least |G(n)| (1–1/n) graphs G G(n) possess the following properties: a) for any k [6log2n], where c=–c log2c–(1–c)×log2(1–c) and c>1/2, we havev
k(G) > C
n
k
(1–1/n2); b) for any k [cn + 5 log2n] we havev
k(G) = C
n
k
. Hence almost all graphs G G(n) containv(G) 2n pairwise nonisomorphic subgraphs.Translated from Matematicheskie Zametki, Vol. 9, No. 3, pp. 263–273, March, 1971. 相似文献
13.
A. A. Sapozhenko 《Mathematical Notes》1968,4(6):881-886
The maximal numberl(f) of conjunctions in a dead-end disjunctive normal form (d.n.f.) of a Boolean functionf and the number (f) of dead-end d.n.f. are important parameters characterizing the complexity of algorithms for finding minimal d.n.f. It is shown that for almost all Boolean functionsl(f)2n–1, log2
(f)2n–1log2nlog2log2n (n).Translated from Matematicheskie Zametki, Vol. 4, No. 6, pp. 649–658, December, 1968. 相似文献
14.
S. V. Petras 《Journal of Mathematical Sciences》1984,24(3):380-386
The behavior of the poles zn(), n=1,2,... of the scattering matrix of the operatorl
u=–u(x), x , (u/n)+(x)u|=0 as 0 is considered. It is proved that |zn()–zn|=0((1/2)qn), where qn is the order of the pole of the scattering matrix for the operator 0u=–u, u/=0.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 117, pp. 183–191, 1981. 相似文献
15.
It is proved that forn 2 the Euclidean ballB
n can be approximated up to (in the Hausdorff distance) by a zonotope havingN summands of equal length withN c(n)(
–2|log|)(n–1)/(n+2).Research supported in part by the U.S.-Israeli Binational Science Foundation. [Please see the Editors' note on the first page of the preceding paper.] 相似文献
16.
Louis Gordon Mark F. Schilling Michael S. Waterman 《Probability Theory and Related Fields》1986,72(2):279-287
Summary For an infinite sequence of independent coin tosses withP(Heads)=p(0,1), the longest run of consecutive heads in the firstn tosses is a natural object of study. We show that the probabilistic behavior of the length of the longest pure head run is closely approximated by that of the greatest integer function of the maximum ofn(1-p) i.i.d. exponential random variables. These results are extended to the case of the longest head run interrupted byk tails. The mean length of this run is shown to be log(n)+klog(n)+(k+1)log(1–p)–log(k!)+k+/–1/2+ r1(n)+ o(1) where log=log1/p
, =0.577 ... is the Euler-Mascheroni constant, =ln(1/p), andr
1(n) is small. The variance is 2/62+1/12 +r
2(n)+ o(1), wherer
2(n) is again small. Upper and lower class results for these run lengths are also obtained and extensions discussed.This work was supported by a grant from the System Development Foundation 相似文献
17.
Kevin O'Bryant 《Journal of Algebraic Combinatorics》2004,19(1):91-115
A Sturmian word is a map W :
{0,1} for which the set of {0, 1}-vectors F
n(W) {(W(i), W(i + 1),...,W(i + n – 1))
T
: i
} has cardinality exactly n + 1 for each positive integer n. Our main result is that the volume of the simplex whose n + 1 vertices are the n + 1 points in F
n(W) does not depend on W. Our proof of this motivates studying algebraic properties of the permutation ,n
(where is any irrational and n is any positive integer) that orders the fractional parts {}, {2},...,{n}, i.e., 0 < {,n
(1)} < {,n
(2)} < ··· < {,n
(n)} < 1. We give a formula for the sign of ,n
, and prove that for every irrational there are infinitely many n such that the order of ,n
(as an element of the symmetric group S
n) is less than n. 相似文献
18.
It is proved for an arbitrary commutative ring A with identity and any integer n3 that if H is a subgroup of GLn(A) normalized by E
n(A,q), then there is an ideal of A such that E
n(A,) H GL
n
(A, (:q40).Furthermore, is uniquely determined up to a certain equivalence relation on the set of ideals of A. The result extends a theorem of Bak, by removing a stability condition he uses on A. 相似文献
19.
In this paper, we have proven that for the Jordan blockS() withS() (SI),
i=1
n
S() =S()
(n)
(n 1) has unique finite (SI) decomposition up to a similarity. As result, we obtain that ifV is a Volterra operator onH=L
2([0, 1]), thenV
(n)
has unique finite (SI) decomposition.This project was supported by National Natural Science Foundation of China. 相似文献
20.
Summary Consider partial sumsS
n
of an i.i.d. sequenceX
1
X
2, ..., of centered random variables having a finite moment generating function in a neighborhood of zero. The asymptotic behaviour of
is investigated, where 1b
n
n denotes an integer sequence such thatb
n
/logn asn. In particular, ifb
n
=o(log
p
n) asn for somep>1, the exact convergence rate ofU
n
/b
n
n
=1 +0 (1) is determined, where
n
depends uponb
n
and the distribution ofX
1. In addition, a weak limit law forU
n
is derived. Finally, it is shown how strong invariance takes over if
b
n
(loglogn)2/log3
n=. 相似文献