Incremental and Decremental Maintenance of Planar Width

We present an algorithm for maintaining the width of a planar point set dynamically, as points are inserted or deleted. Our algorithm takes time O(kn^ε) per update, where k is the amount of change the update causes in the convex hull, n is the number of points in the set, and ε > 0 is any arbitrarily small constant. For incremental or decremental update sequences, the amortized time per update is O(n^ε).     

On improved estimators of the generalized variance

Treated in this paper is the problem of estimating with squared error loss the generalized variance | Σ | from a Wishart random matrix S: p × p W_p(n, Σ) and an independent normal random matrix X: p × k N(ξ, Σ I_k) with ξ(p × k) unknown. Denote the columns of X by X₍₁₎ ,…, X_(k) and set ψ⁽⁰⁾(S, X) = {(n − p + 2)!/(n + 2)!} | S |, ψ⁽ⁱ⁾(X, X) = min[ψ⁽ⁱ⁻¹⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!} | S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |] and Ψ⁽ⁱ⁾(S, X) = min[ψ⁽⁰⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!}| S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |], i = 1,…,k. Our result is that the minimax, best affine equivariant estimator ψ⁽⁰⁾(S, X) is dominated by each of Ψ⁽ⁱ⁾(S, X), i = 1,…,k and for every i, ψ⁽ⁱ⁾(S, X) is better than ψ⁽ⁱ⁻¹⁾(S, X). In particular, ψ^(k)(S, X) = min[{(n − p + 2)!/(n + 2)!} | S |, {(n − p + 2)!/(n + 2)!} | S + X₍₁₎X′₍₁₎|,…,| {(n − p + k + 2)!/(n + k + 2)!} | S + X₍₁₎X′₍₁₎ + + X_(k)X′_(k)|] dominates all other ψ's. It is obtained by considering a multivariate extension of Stein's result (Ann. Inst. Statist. Math. 16, 155–160 (1964)) on the estimation of the normal variance.     

Selection in Monotone Matrices and Computingkth Nearest Neighbors

Anm×nmatrix =(a_{i, j}), 1≤i≤mand 1≤j≤n, is called atotally monotonematrix if for alli₁, i₂, j₁, j₂, satisfying 1≤i₁<i₂≤m, 1≤j₁<j₂≤n.[formula]We present an[formula]time algorithm to select thekth smallest item from anm×ntotally monotone matrix for anyk≤mn. This is the first subquadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm of the same time complexity for ageneralized row-selection problemin monotone matrices. Given a setS={p₁,…, p_n} ofnpoints in convex position and a vectork={k₁,…, k_n}, we also present anO(n^4/3log^c n) algorithm to compute thek_ith nearest neighbor ofp_ifor everyi≤n; herecis an appropriate constant. This algorithm is considerably faster than the one based on a row-selection algorithm for monotone matrices. If the points ofSare arbitrary, then thek_ith nearest neighbor ofp_i, for alli≤n, can be computed in timeO(n^7/5 log^c n), which also improves upon the previously best-known result.     

Manifolds with S 1-category 2 have cyclic fundamental groups

A closed topological n-manifold M ⁿ is of S ¹-category 2 if it can be covered by two open subsets W ₁, W ₂ such that the inclusions W _i → M ⁿ factor homotopically through maps W _i → S ¹. We show that for n > 3 the fundamental group of such an n-manifold is either trivial or infinite cyclic.     

Fundamental groups of manifolds with <Emphasis Type="Italic">S</Emphasis><Superscript>1</Superscript>-category 2

A closed topological n-manifold M ⁿ is of S ¹-category 2 if it can be covered by two open subsets W ₁,W ₂ such that the inclusions W _i → M ⁿ factor homotopically through maps W _i → S ¹ → M ⁿ . We show that the fundamental group of such an n-manifold is a cyclic group or a free product of two cyclic groups with nontrivial amalgamation. In particular, if n = 3, the fundamental group is cyclic.      

A continuous function space with a Faber basis

Let be compact with #S=∞ and let C(S) be the set of all real continuous functions on S. We ask for an algebraic polynomial sequence (P_n)_n=0^∞ with deg P_n=n such that every fC(S) has a unique representation f=∑_i=0^∞ α_iP_i and call such a basis Faber basis. In the special case of , 0<q<1, we prove the existence of such a basis. A special orthonormal Faber basis is given by the so-called little q-Legendre polynomials. Moreover, these polynomials state an example with A(S_q)≠U(S_q)=C(S_q), where A(S_q) is the so-called Wiener algebra and U(S_q) is the set of all fC(S_q) which are uniquely represented by its Fourier series.     

Exact and Approximation Algorithms for Minimum-Width Cylindrical Shells

Let S be a set of n points in \reals ³ . Let \opt be the width (i.e., thickness) of a minimum-width infinite cylindrical shell (the region between two co-axial cylinders) containing S . We first present an O(n ⁵ ) -time algorithm for computing \opt , which as far as we know is the first nontrivial algorithm for this problem. We then present an O(n ^2+δ ) -time algorithm, for any δ>0 , that computes a cylindrical shell of width at most 56\opt containing S . Received May 31, 2000, and in revised form October 25, 2000. Online publication August 29, 2001.     

On the Common Substring Alignment Problem

The Common Substring Alignment Problem is defined as follows: Given a set of one or more strings S₁, S₂ … S_c and a target string T, Y is a common substring of all strings S_i, that is, S_i = B_iYF_i. The goal is to compute the similarity of all strings S_i with T, without computing the part of Y again and again. Using the classical dynamic programming tables, each appearance of Y in a source string would require the computation of all the values in a dynamic programming table of size O(nℓ) where ℓ is the size of Y. Here we describe an algorithm which is composed of an encoding stage and an alignment stage. During the first stage, a data structure is constructed which encodes the comparison of Y with T. Then, during the alignment stage, for each comparison of a source S_i with T, the pre-compiled data structure is used to speed up the part of Y. We show how to reduce the O(nℓ) alignment work, for each appearance of the common substring Y in a source string, to O(n)-at the cost of O(nℓ) encoding work, which is executed only once.     

Embedding Planar Graphs at Fixed Vertex Locations

 Let G be a planar graph of n vertices, v ₁,…,v _n , and let {p ₁,…,p _n } be a set of n points in the plane. We present an algorithm for constructing in O(n ²) time a planar embedding of G, where vertex v _i is represented by point p _i and each edge is represented by a polygonal curve with O(n) bends (internal vertices). This bound is asymptotically optimal in the worst case. In fact, if G is a planar graph containing at least m pairwise independent edges and the vertices of G are randomly assigned to points in convex position, then, almost surely, every planar embedding of G mapping vertices to their assigned points and edges to polygonal curves has at least m/20 edges represented by curves with at least m/40³ bends. Received: May 24, 1999 Final version received: April 10, 2000     

New pseudopolynomial complexity bounds for the bounded and other integer Knapsack related problems

We consider the bounded integer knapsack problem (BKP) , subject to: , and x_j{0,1,…,m_j},j=1,…,n. We use proximity results between the integer and the continuous versions to obtain an O(n³W²) algorithm for BKP, where W=max_j=1,…,nw_j. The respective complexity of the unbounded case with m_j=∞, for j=1,…,n, is O(n²W²). We use these results to obtain an improved strongly polynomial algorithm for the multicover problem with cyclical 1’s and uniform right-hand side.     

Schur functions and the invariant polynomials characterizing U(n) tensor operators

We give a direct formulation of the invariant polynomials _μG_q⁽ⁿ⁾(, Δ_i,;, x_{i,i + 1},) characterizing U(n) tensor operators p, q, …, q, 0, …, 0 in terms of the symmetric functions S_λ known as Schur functions. To this end, we show after the change of variables Δ_i = γ_i − δ_i and x_{i, i + 1} = δ_i − δ_{i + 1} that_μG_q⁽ⁿ⁾(,Δ_i;, x_{i, i + 1},) becomes an integral linear combination of products of Schur functions S_α(, γ_i,) · S_β(, δ_i,) in the variables {γ₁,…, γ_n} and {δ₁,…, δ_n}, respectively. That is, we give a direct proof that _μG_q⁽ⁿ⁾(,Δ_i,;, x_{i, i + 1},) is a bisymmetric polynomial with integer coefficients in the variables {γ₁,…, γ_n} and {δ₁,…, δ_n}. By making further use of basic properties of Schur functions such as the Littlewood-Richardson rule, we prove several remarkable new symmetries for the yet more general bisymmetric polynomials _μ^mG_q⁽ⁿ⁾(γ₁,…, γ_n; δ₁,…, δ_m). These new symmetries enable us to give an explicit formula for both _μ^mG₁⁽ⁿ⁾(γ; δ) and ₁G₂⁽ⁿ⁾(γ; δ). In addition, we describe both algebraic and numerical integration methods for deriving general polynomial formulas for _μ^mG_q⁽ⁿ⁾(γ; δ).     

On Approximate Geometric k -Clustering

For a partition of an n -point set into k subsets (clusters) S ₁ ,S ₂ ,. . .,S _k , we consider the cost function , where c(S _i ) denotes the center of gravity of S _i . For k=2 and for any fixed d and ε >0 , we present a deterministic algorithm that finds a 2-clustering with cost no worse than (1+ε) -times the minimum cost in time O(n log n); the constant of proportionality depends polynomially on ε . For an arbitrary fixed k , we get an O(n log ^k n) algorithm for a fixed ε , again with a polynomial dependence on ε . Received October 19, 1999, and in revised form January 19, 2000.     

An extension of the Erdős–Ginzburg–Ziv Theorem to hypergraphs

An n-set partition of a sequence S is a collection of n nonempty subsequences of S, pairwise disjoint as sequences, such that every term of S belongs to exactly one of the subsequences, and the terms in each subsequence are all distinct with the result that they can be considered as sets. For a sequence S, subsequence S^′, and set T, |T∩S| denotes the number of terms x of S with xT, and |S| denotes the length of S, and SS^′ denotes the subsequence of S obtained by deleting all terms in S^′. We first prove the following two additive number theory results.(1) Let S be a finite sequence of elements from an abelian group G. If S has an n-set partition, A=A₁,…,A_n, such that

then there exists a subsequence S^′ of S, with length |S^′|≤max{|S|−n+1,2n}, and with an n-set partition, , such that . Furthermore, if ||A_i|−|A_j||≤1 for all i and j, or if |A_i|≥3 for all i, then .(2) Let S be a sequence of elements from a finite abelian group G of order m, and suppose there exist a,bG such that . If |S|≥2m−1, then there exists an m-term zero-sum subsequence S^′ of S with or .Let be a connected, finite m-uniform hypergraph, and be the least integer n such that for every 2-coloring (coloring with the elements of the cyclic group ) of the vertices of the complete m-uniform hypergraph , there exists a subhypergraph isomorphic to such that every edge in is monochromatic (such that for every edge e in the sum of the colors on e is zero). As a corollary to the above theorems, we show that if every subhypergraph of contains an edge with at least half of its vertices monovalent in , or if consists of two intersecting edges, then . This extends the Erdős–Ginzburg–Ziv Theorem, which is the case when is a single edge.     

A class of Hamiltonian and edge symmetric Cayley graphs on symmetric groups

Abstract. Let Sn be the symmetric group     

The <Emphasis Type="Italic">f</Emphasis>-Vector of the Descent Polytope

For a positive integer n and a subset S⊆[n−1], the descent polytope DP  _S is the set of points (x ₁,…,x _n ) in the n-dimensional unit cube [0,1] ⁿ such that x _i ≥x _i+1 if i∈S and x _i ≤x _i+1 otherwise. First, we express the f-vector as a sum over all subsets of [n−1]. Second, we use certain factorizations of the associated word over a two-letter alphabet to describe the f-vector. We show that the f-vector is maximized when the set S is the alternating set {1,3,5,…}∩[n−1]. We derive a generating function for F _S (t), written as a formal power series in two non-commuting variables with coefficients in ℤ[t]. We also obtain the generating function for the Ehrhart polynomials of the descent polytopes.     

Finding shortest paths in the plane in the presence of barriers to travel (for any lp - norm)

This paper develops an efficient algorithm for the computation of the shortest paths between given sets of points (origins and destinations) in the plane, when these paths are constrained not to cross any of a finite set of polygonal (open or closed) barriers. It is proved that when distances are measured by an 1_p - norm with 1 < p < ∞, these paths are formed by sequences straight line segments whose intermediate (e.g. apart from origin and destination) end points are barrier vertices. Moreover, only segments that locally support the barriers to which their end points belong are elligible for inclusion in a shortest path. The special case of one origin and one destination is considered, as well as the more general case of many origins and destinations. If n is the number of nodes (origins, destinations and barrier vertices), an algorithm is presented that builds that network of all shortest paths in O(n² log n) time. If the total number of edges in this network is e (bounded by n²), the application of Dijkstra's algorithm enables this computation of the shortest paths from any origin to all destinations in O(e log n) time. If the origins, shortest paths from all origins to all destinations can thus be found in O(ne log n) ≤ O(n^{3 log n}) time.It is also shown that optimal solutions when distances are measured according to the rectilinear or max-norm (i.e. l_p-norm with p = 1 or p = ∞) can be deduced from the results of the algorithm.     

The Weak Convergence for Functions of Negatively Associated Random Variables

Let {X_n, n1} be a sequence of stationary negatively associated random variables, S_j(l)=∑^l_i=1 X_j+i, S_n=∑ⁿ_i=1 X_i. Suppose that f(x) is a real function. Under some suitable conditions, the central limit theorem and the weak convergence for sums are investigated. Applications to limiting distributions of estimators of Var S_n are also discussed.     

A central limit theorem for generalized multilinear forms

Let X₁, …, X_n be independent random variables and define for each finite subset I {1, …, n} the σ-algebra = σ{X_i : i ε I}. In this paper -measurable random variables W_I are considered, subject to the centering condition E(W_I ) = 0 a.s. unless I J. A central limit theorem is proven for d-homogeneous sums W(n) = Σ_{I = d}W_I, with var W(n) = 1, where the summation extends over all (_n^d) subsets I {1, …, n} of size I = d, under the condition that the normed fourth moment of W(n) tends to 3. Under some extra conditions the condition is also necessary.     

Efficient Computation of Rectilinear Geodesic Voronoi Neighbor in the Presence of Obstacles

In this paper we present an algorithm to compute the rectilinear geodesic voronoi neighbor of an arbitrary query pointqamong a setSofmpoints in the presence of a set ofnvertical line segment obstacles inside a rectangular floor. The distance between a pair of points α and β is the shortest rectilinear distance avoiding the obstacles in and is denoted by δ(α, β). The rectilinear geodesic voronoi neighbor of an arbitrary query pointq,RGVN(q) is the pointp_i ∈ Ssuch that δ(q, p_i) is minimum. The algorithm suggests a preprocessing of the elements of the setsSand inO((m + n)log(m + n)) time such that for an arbitrary query pointq, theRGVNquery can be answered inO(log(m + n)) time. The space required for storing the preprocessed information isO(n + m log m). If the points inSare placed on the boundary of the rectangular floor, a different technique is adopted to decrease the space complexity toO(m + n). This technique works even if the obstacles are rectangles instead of line segments. Finally, the parallelization of the preprocessing steps for the latter algorithm is suggested, which takesO(log³(m + n)) time, usingO((m + n)^1.5/log²(m + n)) processors andO(log(m + n)) query time.     

Generalized Ham-Sandwich Cuts

Bárány, Hubard, and Jerónimo recently showed that for given well-separated convex bodies S ₁,…,S _d in R ^d and constants β _i ∈[0,1], there exists a unique hyperplane h with the property that Vol (h ⁺∩S _i )=β _i ⋅Vol (S _i ); h ⁺ is the closed positive transversal halfspace of h, and h is a “generalized ham-sandwich cut.” We give a discrete analogue for a set S of n points in R ^d which are partitioned into a family S=P ₁∪⋅⋅⋅∪P _d of well-separated sets and are in weak general position. The combinatorial proof inspires an O(n(log n) ^d−3) algorithm which, given positive integers a _i ≤|P _i |, finds the unique hyperplane h incident with a point in each P _i and having |h ⁺∩P _i |=a _i . Finally we show two other consequences of the direct combinatorial proof: the first is a stronger result, namely that in the discrete case, the conditions assuring existence and uniqueness of generalized cuts are also necessary; the second is an alternative and simpler proof of the theorem in Bárány et al., and in addition, we strengthen the result via a partial converse.