Dynamic partition trees

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(log² 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=log₂((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).     

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.     

Random Lazy Random Walks on Arbitrary Finite Groups

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 log₂ n where a>1 is constant, then most such walks take no more than a multiple of log₂ n steps to get close to uniformly distributed on G. If k=log₂ n+f(n) where f(n) and f(n)/log₂ n0 as n, then most such walks take no more than a multiple of (log₂ n) ln(log₂ 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.     

Une variante à la Coxeter du groupe de Steinberg

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 G_n() GL _n ()We next determine the kernel of for n = We also give an expression for the generator of the algebraic K group K ₂(Z)of the integers in terms of permutation matrices.     

Partitioning arrangements of lines II: Applications

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 · log^2/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 · log^5/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 ², so that the number of points ofS lying inside a query triangle can be computed inO((n/m) log^3/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.     

Characterizing matchings as the intersection of matroids

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.     

Many triangulated spheres

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 ₁(d)n ^[(d–1)/2], while the known upper bound is logs(d, n)C ₂(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)=2^{0.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.     

Cost Based Filtering for the Constrained Knapsack Problem

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.     

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).     

The complexity and construction of many faces in arrangements of lines and of segments

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) log² 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.     

New Gaussian estimates for enlarged balls

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     

Number of no nisomorphic subgraphs in an n-point graph

LetG(n) be the set of all nonoriented graphs with n enumerated points without loops or multiple lines, and let v_k(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 [6log₂n], where c=–c log₂c–(1–c)×log₂(1–c) and c>1/2, we havev _k(G) > C _n ^k (1–1/n²); b) for any k [cn + 5 log₂n] we havev _k(G) = C _n ^k . Hence almost all graphs G G(n) containv(G) 2ⁿ pairwise nonisomorphic subgraphs.Translated from Matematicheskie Zametki, Vol. 9, No. 3, pp. 263–273, March, 1971.     

On the greatest length of a dead-end disjunctive normal form for almost all Boolean functions

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)2^n–1, log₂ (f)2^n–1log₂nlog₂log₂n (n).Translated from Matematicheskie Zametki, Vol. 4, No. 6, pp. 649–658, December, 1968.     

Perturbation of the poles of the scattering matrix under variation of the boundary condition

The behavior of the poles z_n(), 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 |z_n()–z_n|=0(^(1/2)qn), where q_n is the order of the pole of the scattering matrix for the operator ₀u=–u, u/=0.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 117, pp. 183–191, 1981.     

Approximating the ball by a minkowski sum of segments with equal length

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.]     

An extreme value theory for long head runs

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+ r₁(n)+ o(1) where log=log_1/p , =0.577 ... is the Euler-Mascheroni constant, =ln(1/p), andr ₁(n) is small. The variance is ₂/6²+1/12 +r ₂(n)+ o(1), wherer ₂(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     

Sturmian Words and the Permutation that Orders Fractional Parts

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.     

A generalized sandwich theorem

It is proved for an arbitrary commutative ring A with identity and any integer n3 that if H is a subgroup of GL_n(A) normalized by E _n(A,q), then there is an ideal of A such that E _n(A,) H GL _n (A, (:q⁴⁰).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.     

On the unique finite (SI) decomposition of the Jordan operator ⊕ i=1 n S(θ) for certain inner function θ

In this paper, we have proven that for the Jordan blockS() withS() (SI), _i=1 ⁿ S() =S() ⁽ⁿ⁾ (n 1) has unique finite (SI) decomposition up to a similarity. As result, we obtain that ifV is a Volterra operator onH=L ²([0, 1]), thenV ⁽ⁿ⁾ has unique finite (SI) decomposition.This project was supported by National Natural Science Foundation of China.     

Exact convergence rates in strong approximation laws for large increments of partial sums

Summary Consider partial sumsS _n of an i.i.d. sequenceX ₁ X ₂, ..., 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 ₁. In addition, a weak limit law forU _n is derived. Finally, it is shown how strong invariance takes over if b _n (loglogn)²/log³ n=.