Optimal Partition Trees

We revisit one of the most fundamental classes of data structure problems in computational geometry: range searching. Matoušek (Discrete Comput. Geom. 10:157–182, 1993) gave a partition tree method for d-dimensional simplex range searching achieving O(n) space and O(n ^1−1/d ) query time. Although this method is generally believed to be optimal, it is complicated and requires O(n ^1+ε ) preprocessing time for any fixed ε>0. An earlier method by Matoušek (Discrete Comput. Geom. 8:315–334, 1992) requires O(nlogn) preprocessing time but O(n ^1−1/d log ^O(1) n) query time. We give a new method that achieves simultaneously O(nlogn) preprocessing time, O(n) space, and O(n ^1−1/d ) query time with high probability. Our method has several advantages:

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.     

Diameter,width, closest line pair,and parametric searching

We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved solutions for them. We obtain, for any fixed ε>0, anO(n ^1+ε) algorithm for computing the diameter of a point set in 3-space, anO(^8/5+ε) algorithm for computing the width of such a set, and onO(n ^8/5+ε) algorithm for computing the closest pair in a set ofn lines in space. All these algorithms are deterministic. Work by Bernard Chazelle was supported by NSF Grant CCR-90-02352. Work by Herbert Edelsbrunner was supported by NSF Grant CCR-89-21421. Work by Leonidas Guibas and Micha Sharir was supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Micha Sharir was also supported by ONR Grant N00014-90-J-1284, by NSF Grant CCR-89-01484, and by grants from the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

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.     

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.     

Semidiscrete and asymptotic approximations for the nonstationary radiative–conductive heat transfer problem in a periodic system of grey heat shields

We consider semidiscrete and asymptotic approximations to a solution to the nonstationary nonlinear initial-boundary-value problem governing the radiative–conductive heat transfer in a periodic system consisting of n grey parallel plate heat shields of width ε = 1/n, separated by vacuum interlayers. We study properties of special semidiscrete and homogenized problems whose solutions approximate the solution to the problem under consideration. We establish the unique solvability of the problem and deduce a priori estimates for the solutions. We obtain error estimates of order O( ?{e} ) O\left( {\sqrt {\varepsilon } } \right) and O(ε) for semidiscrete approximations and error estimates of order O( ?{e} ) O\left( {\sqrt {\varepsilon } } \right) and O(ε ^3/4) for asymptotic approximations. Bibliography: 9 titles.     

Cutting hyperplane arrangements

We consider a collectionH ofn hyperplanes in E ^d (where the dimensiond is fixed). An ε-cutting forH is a collection of (possibly unbounded)d-dimensional simplices with disjoint interors, which cover all E ^d and such that the interior of any simplex is intersected by at mostεn hyperplanes ofH. We give a deterministic algorithm for finding a (1/r)-cutting withO(r ^d ) simplices (which is asymptotically optimal). Forr≤n ^1−σ, where δ>0 is arbitrary but fixed, the running time of this algorithm isO(n(logn) ^O(1) r ^d−1). In the plane we achieve a time boundO(nr) forr≤n ^1−δ, which is optimal if we also want to compute the collection of lines intersecting each simplex of the cutting. This improves a result of Agarwal, and gives a conceptually simpler algorithm. For ann point setX⊆E ^d and a parameterr, we can deterministically compute a (1/r)-net of sizeO(rlogr) for the range space (X, {X ϒ R; R is a simplex}), In timeO(n(logn) ^O(1) r ^d−1 +r ^O(1)). The size of the (1/r)-net matches the best known existence result. By a simple transformation, this allows us to find ε-nets for other range spaces usually encountered in computational geometry. These results have numerous applications for derandomizing algorithms in computational geometry without affecting their running time significantly. A preliminary version of this paper appeared inProceedings of the Sixth ACM Symposium on Computational Geometry, Berkeley, 1990, pp. 1–9. Work on this paper was supported by DIMACS Center.     

Lip Automorphism Germ and Lip Automorphism

Let X be a metric space, ε^n(X) be the standard trivial Lip n-bundle over X, and Φ be a Lip automorphism germ of ε^n(X). This paper proves that there is a Lip automorphism Φ‘ of ε^n(X) such that the germ of Φ‘ is Φ.     

Almost tight upper bounds for the single cell and zone problems in three dimensions

We consider the problem of bounding the combinatorial complexity of a single cell in an arrangement ofn low-degree algebraic surface patches in 3-space. We show that this complexity isO(n ^2+ε), for any ε>0, where the constant of proportionality depends on ε and on the maximum degree of the given surfaces and of their boundaries. This extends several previous results, almost settles a 9-year-old open problem, and has applications to motion planning of general robot systems with three degrees of freedom. As a corollary of the above result, we show that the overall complexity of all the three-dimensional cells of an arrangement ofn low-degree algebraic surface patches, intersected by an additional low-degree algebraic surface patch σ (the so-calledzone of σ in the arrangement) isO(n ^2+ε), for any ε>0, where the constant of proportionality depends on ε and on the maximum degree of the given surfaces and of their boundaries. Work on this paper by the first author has been supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA Grant IRI-9306544, and by NSF Grant CCR-9215219. Work on this paper by the second author has been supported by NSF Grants CCR-91-22103 and CCR-93-111327, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F., the German-Israeli Foundation for Scientific Research and Development, and the Israel Science Fund administered by the Israeli Academy of Sciences.     

Euclidean minimum spanning trees and bichromatic closest pairs

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 log² n+n log² m) inE ₃, which yields anO(N ^4/3 log^4/3 N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE ³. 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).     

Isomorphic embedding of ℓ p n , 1<p<2, into ℓ 1 (1+ε)n

In this paper we partially answer a question posed by V. Milman and G. Schechtman by proving that ℓ _p ⁿ , (C logn)^1/q(1+1/ε)-embeds into ℓ ₁ ^(1+ε)n , where 1<p<2 and 1/p+1/q=1. Supported by ISF.     

On generalized energy equality of the Navier-Stokes equations

We show that for every initial dataa εL ²(Ω) there exists a weak solutionu of the Navier-Stokes equations satisfying the generalized energy inequality introduced by Caffarelli-Kohn-Nirenberg forn=3. We also show that if a weak solutionu εL ^s (0,T;L ^q (Ω)) with 2/q + 2/s ≤ 1 and 3/q + 1/s ≤ 1 forn=3, or 2/q + 2/s ≤ 1 andq ≥ 4 forn ≥ 4, thenu satisfies both the generalized and the usual energy equalities. Moreover we show that the generalized energy equality holds only under the local hypothesis thatu εL ^s (ε, T; L ^q (K)) for all compact setsK ⊂ ⊂ Ω and all 0 <ε <T with the same (q, s) as above when 3 ≤n ≤ 10.     

On Regular Vertices of the Union of Planar Convex Objects

Let be a collection of n compact convex sets in the plane such that the boundaries of any pair of sets in intersect in at most s points for some constant s≥4. We show that the maximum number of regular vertices (intersection points of two boundaries that intersect twice) on the boundary of the union U of is O ^*(n ^4/3), which improves earlier bounds due to Aronov et al. (Discrete Comput. Geom. 25, 203–220, 2001). The bound is nearly tight in the worst case. In this paper, a bound of the form O ^*(f(n)) means that the actual bound is C _ε f(n)⋅n ^ε for any ε>0, where C _ε is a constant that depends on ε (and generally tends to ∞ as ε decreases to 0). Work by János Pach and Micha Sharir was supported by NSF Grant CCF-05-14079, and by a grant from the U.S.–Israeli Binational Science Foundation. Work by Esther Ezra and Micha Sharir was supported by grant 155/05 from the Israel Science Fund and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. Work on this paper by the first author has also been supported by an IBM Doctoral Fellowship. A preliminary version of this paper has been presented in Proc. 23nd Annu. ACM Sympos. Comput. Geom., 2007, pp. 220–226. E. Ezra’s current address: Department of Computer Science, Duke University, Durham, NC 27708-0129, USA. E-mail: esther@cs.duke.edu     

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.     

Special representations of the groups U(∞, 1) and O(∞, 1) and the associated representations of the current groups U(∞, 1) X and O(∞, 1) X in quasi-poisson spaces

A method for constructing representations of the current groups O(n, 1) ^X and U(n, 1) ^X , n ε ℕ, developed in the previous papers by the authors is generalized to the case of infinite n. This leads to an interesting difference in construction (absent for finite n) between the cases of the orthogonal and unitary groups, which is due to the different character of special representations of the groups of coefficients.     

Laplace transforms of polynomially bounded vector-valued functions and semigroups of operators

We define an invariant of measure-theoretic isomorphism for dynamical systems, as the growth rate inn of the number of small -balls aroundα-n-names necessary to cover most of the system, for any generating partitionα. We show that this rate is essentially bounded if and only if the system is a translation of a compact group, and compute it for several classes of systems of entropy zero, thus getting examples of growth rates inO(n),O(n ^k ) fork ε ℕ, oro(f(n)) for any given unboundedf, and of various relationships with the usual notion of language complexity of the underlying topological system.     

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 Exceptional Set in Hua＇s Theorem for Three Squares of Primes

It is proved that with at most O(N^11/12 c) exceptions, all positive integers n ≤ N satisfying some necessary congruence conditions are the sum of three squares of primes. This improves substantially the previous results in this direction.     

Small Hop-diameter Sparse Spanners for Doubling Metrics

Given a metric M=(V,d), a graph G=(V,E) is a t-spanner for M if every pair of nodes in V has a “short” path (i.e., of length at most t times their actual distance) between them in the spanner. Furthermore, this spanner has a hop diameter bounded by D if every pair of nodes has such a short path that also uses at most D edges. We consider the problem of constructing sparse (1+ε)-spanners with small hop diameter for metrics of low doubling dimension. In this paper, we show that given any metric with constant doubling dimension k and any 0<ε<1, one can find (1+ε)-spanner for the metric with nearly linear number of edges (i.e., only O(nlog ^* n+n ε ^−O(k)) edges) and constant hop diameter; we can also obtain a (1+ε)-spanner with linear number of edges (i.e., only n ε ^−O(k) edges) that achieves a hop diameter that grows like the functional inverse of Ackermann’s function. Moreover, we prove that such tradeoffs between the number of edges and the hop diameter are asymptotically optimal. The conference version of the paper appeared in ACM-SIAM SODA 2006. This research of T.-H.H. Chan was done while the author was at Carnegie Mellon University and was partly supported by the NSF grant CCR-0122581 (the ALADDIN project), the NSF CAREER award CCF-0448095, and by an Alfred P. Sloan Fellowship. This research of A. Gupta was partly supported by the NSF grant CCR-0122581 (the ALADDIN project), the NSF CAREER award CCF-0448095, and by an Alfred P. Sloan Fellowship.     

A result on Waring–Goldbach problem for cubes

In this paper, we prove that, with at most O(N ^5/6+ε ) exceptions, all positive integers n ⩽ N can be written as sums of a cube and four cubes of primes.