Dimensionality Reductions in ℓ<Subscript>2</Subscript> that Preserve Volumes and Distance to Affine Spaces

Let X be a subset of n points of the Euclidean space, and let 0 < ε < 1. A classical result of Johnson and Lindenstrauss [JL] states that there is a projection of X onto a subspace of dimension O(ε^-2 log n) with distortion ≤ 1+ ε. We show a natural extension of the above result to a stronger preservation of the geometry of finite spaces. By a k-fold increase of the number of dimensions used compared with [JL], a good preservation of volumes and of distances between points and affine spaces is achieved. Specifically, we show how to embed a subset of size n of the Euclidean space into a O(ε^-2 log n)-dimensional Euclidean space, so that no set of size s ≤ k changes its volume by more than (1 + ε^s-1. Moreover, distances of points from affine hulls of sets of at most k - 1 points in the space do not change by more than a factor of 1 + ε. A consequence of the above with k = 3 is that angles can be preserved using asymptotically the same number of dimensions as the one used in [JL]. Our method can be applied to many problems with high-dimensional nature such as Projective Clustering and Approximated Nearest Affine Neighbour Search. In particular, it shows a first polylogarithmic query time approximation algorithm to the latter. We also show a structural application that for volume respecting embedding in the sense introduced by Feige [F], the host space need not generally be of dimensionality greater than polylogarithmic in the size of the graph.     

A sparse graph almost as good as the complete graph on points inK dimensions

A setV ofn points ink-dimensional space induces a complete weighted undirected graph as follows. The points are the vertices of this graph and the weight of an edge between any two points is the distance between the points under someL _p metric. Let ε≤1 be an error parameter and letk be fixed. We show how to extract inO(n logn+ε ^−k log(1/ε)n) time a sparse subgraphG=(V, E) of the complete graph onV such that: (a) for any two pointsx, y inV, the length of the shortest path inG betweenx andy is at most (1+∈) times the distance betweenx andy, and (b)|E|=O(ε^−k n).     

The Effect of Corners on the Complexity of Approximate Range Searching

Given an n-element point set in ℝ ^d , the range searching problem involves preprocessing these points so that the total weight, or for our purposes the semigroup sum, of the points lying within a given query range η can be determined quickly. In ε-approximate range searching we assume that η is bounded, and the sum is required to include all the points that lie within η and may additionally include any of the points lying within distance ε⋅diam(η) of η’s boundary. In this paper we contrast the complexity of approximate range searching based on properties of the semigroup and range space. A semigroup (S,+) is idempotent if x+x=x for all x∈S, and it is integral if for all k≥2, the k-fold sum x+⋅⋅⋅+x is not equal to x. Recent research has shown that the computational complexity of approximate spherical range searching is significantly lower for idempotent semigroups than it is for integral semigroups in terms of the dependencies on ε. In this paper we consider whether these results can be generalized to other sorts of ranges. We show that, as with integrality, allowing sharp corners on ranges has an adverse effect on the complexity of the problem. In particular, we establish lower bounds on the worst-case complexity of approximate range searching in the semigroup arithmetic model for ranges consisting of d-dimensional unit hypercubes under rigid motions. We show that for arbitrary (including idempotent) semigroups and linear space, the query time is at least . In the case of integral semigroups we prove a tighter lower bound of Ω(1/ε ^d−2). These lower bounds nearly match existing upper bounds for arbitrary semigroups. In contrast, we show that the improvements offered by idempotence do apply to smooth convex ranges. We say that a range is smooth if at every boundary point there is an incident Euclidean sphere that lies entirely within the range whose radius is proportional to the range’s diameter. We show that for smooth ranges and idempotent semigroups, ε-approximate range queries can be answered in O(log n+(1/ε)^(d−1)/2log (1/ε)) time using O(n/ε) space. We show that this is nearly tight by presenting a lower bound of Ω(log n+(1/ε)^(d−1)/2). This bound is in the decision-tree model and holds irrespective of space. A preliminary version of this paper appeared in the Proc. 22nd Annu. ACM Sympos. Comput. Geom., pp. 11–20, 2006. The research of S. Arya was supported by the Research Grants Council, Hong Kong, China under project number HKUST6184/04E. The research of D.M. Mount was partially supported by the National Science Foundation under grant CCR-0635099 and the Office of Naval Research under grant N00014-08-1-1015.     

Kinetic Spanners in ℝ<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>

We present a new (1+ε)-spanner for sets of n points in ℝ ^d . Our spanner has size O(n/ε ^d−1) and maximum degree O(log  ^d n). The main advantage of our spanner is that it can be maintained efficiently as the points move: Assuming that the trajectories of the points can be described by bounded-degree polynomials, the number of topological changes to the spanner is O(n ²/ε ^d−1), and using a supporting data structure of size O(nlog  ^d n), we can handle events in time O(log  ^d+1 n). Moreover, the spanner can be updated in time O(log n) if the flight plan of a point changes. This is the first kinetic spanner for points in ℝ ^d whose performance does not depend on the spread of the point set.     

Robust Shape Fitting via Peeling and Grating Coresets

Let P be a set of n points in ℝ ^d . A subset of P is called a (k,ε)-kernel if for every direction, the directional width of ε-approximates that of P, when k “outliers” can be ignored in that direction. We show that a (k,ε)-kernel of P of size O(k/ε ^(d−1)/2) can be computed in time O(n+k ²/ε ^d−1). The new algorithm works by repeatedly “peeling” away (0,ε)-kernels from the point set. We also present a simple ε-approximation algorithm for fitting various shapes through a set of points with at most k outliers. The algorithm is incremental and works by repeatedly “grating” critical points into a working set, till the working set provides the required approximation. We prove that the size of the working set is independent of n, and thus results in a simple and practical, near-linear ε-approximation algorithm for shape fitting with outliers in low dimensions. We demonstrate the practicality of our algorithms by showing their empirical performance on various inputs and problems. A preliminary version of this paper appeared in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 182–191. P.A. and H.Y. are supported by NSF under grants CCR-00-86013, EIA-01-31905, CCR-02-04118, and DEB-04-25465, by ARO grants W911NF-04-1-0278 and DAAD19-03-1-0352, and by a grant from the U.S.–Israel Binational Science Foundation. S.H.-P. is supported by a NSF CAREER award CCR-0132901.     

Range Minima Queries with Respect to a Random Permutation,and Approximate Range Counting

In approximate halfspace range counting, one is given a set P of n points in ℝ ^d , and an ε>0, and the goal is to preprocess P into a data structure which can answer efficiently queries of the form: Given a halfspace h, compute an estimate N such that (1−ε)|P∩h|≤N≤(1+ε)|P∩h|.     

Asymptotic analysis of a parabolic semilinear problem with nonlinear boundary multiphase interactions in a perforated domain

We consider a parabolic semilinear problem with rapidly oscillating coefficients in a domain Ω_ε that is ε-periodically perforated by small holes of size O\mathcal {O}(ε). The holes are divided into two ε-periodical sets depending on the boundary interaction at their surfaces, and two different nonlinear Robin boundary conditions σ_ε(u _ε) + εκ _m (u _ε) = εg ^(m) _ε, m = 1, 2, are imposed on the boundaries of holes. We study the asymptotics as ε → 0 and establish a convergence theorem without using extension operators. An asymptotic approximation of the solution and the corresponding error estimate are also obtained. Bibliography: 60 titles. Illustrations: 1 figure.     

Rank-two update algorithms for the minimum volume enclosing ellipsoid problem

We consider the problem of computing a (1+ε)-approximation to the minimum volume enclosing ellipsoid (MVEE) of a given set of m points in R ⁿ . Based on the idea of sequential minimal optimization (SMO) method, we develop a rank-two update algorithm. This algorithm computes an approximate solution to the dual optimization formulation of the MVEE problem, which updates only two weights of the dual variable at each iteration. We establish that this algorithm computes a (1+ε)-approximation to MVEE in O(mn ³/ε) operations and returns a core set of size O(n ²/ε) for ε∈(0,1). In addition, we give an extension of this rank-two update algorithm. Computational experiments show the proposed algorithms are very efficient for solving large-scale problem with a high accuracy.     

On eigenfunctions localized in a neighborhood of the lateral surface of a thin domain

We study the spectrum of the boundary-value problem for the Laplace operator in a thin domain Ω(ε) obtained by small perturbation of the cylinder Ω(ε)=ω×(-ε/2.ε/2) ⊂ ℝ³in a neighborhood of the lateral surface. The Dirichlet condition is imposed on the bases of the cylinder, and the Dirichlet condition or the Neumann condition is imposed on the remaining part of ∂Ω(ε). We construct and justify asymptotic formulas (as ε→+0) for eigenvalues and eigenfunctions. In view of a special form of the lateral surface, there are eigenfunctions of boundary-layer type that exponentially decrease far from the lateral surface. For the mixed boundary-value problem such a localization is possible in neighborhoods of local maxima of the curvature of the contour ∂ω. This property of eigenfunctions is a characteristic feature of the first points of the spectrum (in particular, the first eigenvalue) and, under the passage from Ω(h)₍₎ to Ω(h), the spectrum itself has perturbation O(h⁻²). Bibliography: 29 titles. Translated fromProblemy Matematicheskogo Analiza, No. 19, 1999, pp. 105–149.     

Computing Minimum-Volume Enclosing Axis-Aligned Ellipsoids

Given a set of points and ε>0, we propose and analyze an algorithm for the problem of computing a (1+ε)-approximation to the minimum-volume axis-aligned ellipsoid enclosing . We establish that our algorithm is polynomial for fixed ε. In addition, the algorithm returns a small core set , whose size is independent of the number of points m, with the property that the minimum-volume axis-aligned ellipsoid enclosing is a good approximation of the minimum-volume axis-aligned ellipsoid enclosing . Our computational results indicate that the algorithm exhibits significantly better performance than the theoretical worst-case complexity estimate. This work was supported in part by the National Science Foundation through CAREER Grants CCF-0643593 and DMI-0237415.     

Approximation Algorithms for Minimum-Width Annuli and Shells

Let S be a set of n points in \re ^d . The ``roundness' of S can be measured by computing the width ω ^* =ω ^* (S) of the thinnest spherical shell (or annulus in \re ² ) that contains S . This paper contains two main results related to computing an approximation of ω ^* : (i) For d=2 , we can compute in O(n log n) time an annulus containing S whose width is at most 2ω ^* (S) . We extend this algorithm, so that, for any given parameter ε >0 , an annulus containing S whose width is at most (1+ε )ω ^* is computed in time O(n log n + n/ε ² ) . (ii) For d \geq 3 , given a parameter ε > 0 , we can compute a shell containing S of width at most (1+ε)ω ^* either in time O ( n / ε ^d ) log ( \Delata / ω ^* ε ) or in time O ( n / ε ^d-2 ) log n + 1 / εlog \Delata / ω ^* ε , where Δ is the diameter of S . Received July 6, 1999, and in revised form April 17, 2000. Online publication August\/ 11, 2000.     

Homogenization of eigenvalue problems in perforated domains

In this paper, we treat some eigenvalue problems in periodically perforated domains and study the asymptotic behaviour of the eigenvalues and the eigenvectors when the number of holes in the domain increases to infinity Using the method of asymptotic expansion, we give explicit formula for the homogenized coefficients and expansion for eigenvalues and eigenvectors. If we denote by ε the size of each hole in the domain, then we obtain the following aysmptotic expansion for the eigenvalues: Dirichlet: λ_ε = ε⁻² λ + λ₀ +O (ε), Stekloff: λ_ε = ελ₁ +O (ε²), Neumann: λ_ε = λ₀ + ελ₁ +O (ε²). Using the method of energy, we prove a theorem of convergence in each case considered here. We briefly study correctors in the case of Neumann eigenvalue problem.     

Pinching, Pontrjagin classes, and negatively curved vector bundles

We prove several finiteness results for the class ℳ_a,b,π,n of n-manifolds that have fundamental groups isomorphic to π and that can be given complete Riemannian metrics of sectional curvatures within {a,b} where a≤b<0. In particular, if M is a closed negatively curved manifold of dimension at least three, then only finitely many manifolds in the class ℳ_a,b,π1(M),n are total spaces of vector bundles over M. Furthermore, given a word-hyperbolic group π and an integer n there exists a positive ε=ε(n,π) such that the tangent bundle of any manifold in the class ℳ_{-1-ε, -1, π, n} has zero rational Pontrjagin classes. Oblatum 27-IX-1999 & 17-XI-2000?Published online: 5 March 2001     

A generic approach to approximate efficiency and applications to vector optimization with set-valued maps

In this paper we focus on approximate minimal points of a set in Hausdorff locally convex spaces. Our aim is to develop a general framework from which it is possible to deduce important properties of these points by applying simple results. For this purpose we introduce a new concept of ε-efficient point based on set-valued mappings and we obtain existence results and properties on the behavior of these approximate efficient points when ε is fixed and by considering that ε tends to zero. Finally, the obtained results are applied to vector optimization problems with set-valued mappings.     

Homogenization of Nonlinear Degenerate Non-monotone Elliptic Operators in Domains Perforated with Tiny Holes

The paper deals with the homogenization problem beyond the periodic setting, for a degenerated nonlinear non-monotone elliptic type operator on a perforated domain Ω ^ε in ℝ ^N with isolated holes. While the space variable in the coefficients a ₀ and a is scaled with size ε (ε>0 a small parameter), the system of holes is scaled with ε ² size, so that the problem under consideration is a reiterated homogenization problem in perforated domains. The homogenization problem is formulated in terms of the general, so-called deterministic homogenization theory combining real homogenization algebras with the Σ-convergence method. We present a new approach based on the Besicovitch type spaces to solve deterministic homogenization problems, and we obtain a very general abstract homogenization results. We then illustrate this abstract setting by providing some concrete applications of these results to, e.g., the periodic homogenization, the almost periodic homogenization, and others.     

Weierstrass points on trigonal curves I: The ramification points

LetC be a smooth curve of genusg≥5. Assume thatP is a Weierstrass point onC which first non-gap is equal to 3. The gap sequence atP is completely determinated by numbersn and ε satisfying (g−1)/3≤n≤g/2 and ε is 1 or 2 as follows. Given suchn and ε, the corresponding gap sequence is (1, 2, 4, 5,…, 3n−2, 3n−1, 3n+ε, 3n+3+ε, …, 3(g−n−1)+ε). We say thatP is of then-th kind andP is of type I (resp. II) if ε=1 (resp. 2). Because a curve of genusg≥5 has at most one linear systemg1/3, it follows that the Weierstrass points onC with first non-gap equal to 3 are of the same kind.     

Random Subgraphs Of Finite Graphs: III. The Phase Transition For The n-Cube

We study random subgraphs of the n-cube {0,1}ⁿ, where nearest-neighbor edges are occupied with probability p. Let p_c(n) be the value of p for which the expected size of the component containing a fixed vertex attains the value λ2^n/3, where λ is a small positive constant. Let ε=n(p−p_c(n)). In two previous papers, we showed that the largest component inside a scaling window given by |ε|=Θ(2^−n/3) is of size Θ(2^2n/3), below this scaling window it is at most 2(log 2)nε⁻², and above this scaling window it is at most O(ε2ⁿ). In this paper, we prove that for the size of the largest component is at least Θ(ε2ⁿ), which is of the same order as the upper bound. The proof is based on a method that has come to be known as “sprinkling,” and relies heavily on the specific geometry of the n-cube.     

A Lower Bound for Weak ɛ -Nets in High Dimension

   Abstract. A finite set N ⊂ R ^d is a weak ε-net for an n -point set X ⊂ R ^d (with respect to convex sets) if it intersects each convex set K with |K ∩ X| ≥ ε n . It is shown that there are point sets X ⊂ R ^d for which every weak ε -net has at least const ⋅