The Discrepancy of Boxes in Higher Dimension

We prove that the red—blue discrepancy of the set system formed by n points and n axis-parallel boxes in <bo>R</bo> ^d can be as high as n ^Ω(1) in any dimension d= Ω(log n) . This contrasts with the fixed-dimensional case d=O(1) , where the discrepancy is always polylogarithmic. More generally we show that in any dimension 1<d= O(log n) the maximum discrepancy is 2 ^Ω(d) . Our result also leads to a new lower bound on the complexity of off-line orthogonal range searching. This is the problem of summing up weights in boxes, given n weighted points and n boxes in <bo>R</bo> ^d . We prove that the number of arithmetic operations is at least Ω(nd+ nlog log n) in any dimension d=O(log n) . Received June 30, 2000, and in revised form November 9, 2000. Online publication April 6, 2001.     

The cauchy problem at simply characteristic points andP-convexity

Summary Let Ω cR ⁿ be an open set and let P be a linear partial differential operator with constant coefficients inR ⁿ. Then Ω is said to be P-convex if for each f ε C^∞(Ω) there is a u ε D′(Ω) such that P(D)u=f. A complete geometric characterization of P-convex sets inR ³ is given when P is of principal type and when Ω has C²-boundary. As a step in the proof one also obtains necessary and sufficient conditions for uniqueness in the local Cauchy problem at simply characteristic points inR ³. The tools are a sophisticated use of the author's uniqueness cones on one hand and his semi-global nullsolutions on the other hand. Hints are given on the difficulties that may be encountered inR ⁿ for the same problem. Entrata in Redazione il 7 giugno 1978.     

A Trace Bound for the Hereditary Discrepancy

Let A be the incidence matrix of a set system with m sets and n points, m ≤ n , and let t= \mathop \rm tr M , where M= A ^T A . Finally, let σ = \mathop \rm tr M ² be the sum of squares of the elements of M . We prove that the hereditary discrepancy of the set system is at least . This general trace bound allows us to resolve discrepancy-type questions for which spectral methods had previously failed. Also, by using this result in conjunction with the spectral lemma for linear circuits, we derive new complexity bounds for range searching. We show that the (red—blue) discrepancy of the set system formed by n points and n lines in the plane is Ω(n ^1/6 ) in the worst case and always ¹ \tilde O(n ^1/6 ) . We give a simple explicit construction of n points and n halfplanes with hereditary discrepancy \tildeΩ(n ^1/4 ) . We show that in any dimension d= Ω( log n/\kern -1ptlog log n ) , there is a set system of n points and n axis-parallel boxes in \bf R ^d with discrepancy n ^{Ω(1/\kern -1pt log log n)} . Applying these discrepancy results together with a new variation of the spectral lemma, we derive a lower bound of Ω(nlog n) on the arithmetic complexity of off-line range searching for points and lines (for nonmonotone circuits). We also prove a lower bound of Ω(nlog n/\kern -1ptlog log n) on the complexity of orthogonal range searching in any dimension Ω(log n/\kern -1ptlog log n) . ¹ We use the notation \tilde O(m) and \tilde Ω(m) as shorthand for O(mlog ^c m) and Ω(m/\kern -1ptlog ^c m) , respectively, for some constant c>0 . Received April 5, 2000, and in revised form October 17, 2000. Online publication June 22, 2001.     

Strong approximation ofGSBV functions by piecewise smooth functions

Let Ω be an open and bounded subset ofR ⁿ with locally Lipschitz boundary. We prove that the functionsv∈SBV(Ω,R ^m ) whose jump setS _vis essentially closed and polyhedral and which are of classW ^{k, ∞} (S _v,R ^m) for every integerk are strongly dense inGSBV ^p(Ω,R ^m ), in the sense that every functionu inGSBV ^p(Ω,R ^m ) is approximated inL ^p(Ω,R ^m ) by a sequence of functions {v _k{_j∈N with the described regularity such that the approximate gradients ∇v _jconverge inL ^p(Ω,R ^nm ) to the approximate gradient ∇u and the (n−1)-dimensional measure of the jump setsS _{v j} converges to the (n−1)-dimensional measure ofS _u. The structure ofS _v can be further improved in casep≤2.

---

Sunto Sia Ω un aperto limitato diR ⁿ con frontiera localmente Lipschitziana. In questo lavoro si dimostra che le funzioniv∈SBV(Ω,R ^m ) con insieme di saltoS _v essenzialmente chiuso e poliedrale che sono di classeW ^{k, ∞} (S _v,R ^m ) per ogni interok sono fortemente dense inGSBV ^p(Ω,R ^m ), nel senso che ogni funzioneu∈GSBV ^p(Ω,R ^m ) è approssimata inL ^p(Ω,R ^m ) da una successione di funzioni {v _j}_j∈N con la regolaritá descritta tali che i gradienti approssimati ∇v _jconvergono inL ^p(Ω,R ^nm ) al gradiente approssimato ∇u e la misura (n−1)-dimensionale degli insiemi di saltoS _{v j}converge alla misura (n−1)-dimensionale diS _u. La struttura diS _vpuó essere migliorata nel caso in cuip≤2.

     

An optimal convex hull algorithm in any fixed dimension

We present a deterministic algorithm for computing the convex hull ofn points inE ^d in optimalO(n logn+n ^⌞d/2⌟ ) time. Optimal solutions were previously known only in even dimension and in dimension 3. A by-product of our result is an algorithm for computing the Voronoi diagram ofn points ind-space in optimalO(n logn+n ^⌜d/2⌝ ) time. This research was supported in part by the National Science Foundation under Grant CCR-9002352 and The Geometry Center, University of Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc. A preliminary version of this paper has appeared in “An optimal convex hull algorithm and new results on cuttings”,Proceedings of the 32nd Annual IEEE Symposium on the Foundations of Computer Science, October 1991, pp. 29–38. The convex hull algorithm given in the present paper, although similar in spirit, is considerably simpler than the one given in the proceedings.     

Better lower bounds on detecting affine and spherical degeneracies

We show that in the worst case, Ω(n ^d ) sidedness queries are required to determine whether a set ofn points in ℝ ^d is affinely degenerate, i.e., whether it containsd+1 points on a common hyperplane. This matches known upper bounds. We give a straightforward adversary argument, based on the explicit construction of a point set containing Ω(n ^d ) “collapsible” simplices, any one of which can be made degenerate without changing the orientation of any other simplex. As an immediate corollary, we have an Ω(n ^d ) lower bound on the number of sidedness queries required to determine the order type of a set ofn points in ℝ ^d . Using similar techniques, we also show that Ω(n ^d+1) in-sphere queries are required to decide the existence of spherical degeneracies in a set ofn points in ℝ ^d . An earlier version of this paper was presented at the 34th Annual IEEE Symposium on Foundations of Computer Science [8]. This research has been supported by NSF Presidential Young Investigator Grant CCR-9058440.     

Harmonic maps from manifolds of <Emphasis Type="Italic">L</Emphasis><Superscript>∞</Superscript>-Riemannian metrics

For a bounded domain Ω ⊂ R ⁿ endowed with L ^∞-metric g, and a C ⁵-Riemannian manifold (N, h) ⊂ R ^k without boundary, let u ∈ W ^1,2(Ω, N) be a weakly harmonic map, we prove that (1) u ∈ C ^α (Ω, N) for n = 2, and (2) for n ≥ 3, if, in additions, g ∈ VMO(Ω) and u satisfies the quasi-monotonicity inequality (1.5), then there exists a closed set Σ ⊂ Ω, with H ^n-2(Σ) = 0, such that for some α ∈ (0, 1). C. Y. Wang Partially supported by NSF.     

Potential space estimates in local Hardy spaces for Green potentials in convex domains

Let Ω be a bounded co.nvex domain in Rn(n≥3) and G(x,y) be the Green function of the Laplace operator -△ on Ω. Let hrp(Ω) = {f ∈ D'(Ω) :(E)F∈hp(Rn), s.t. F|Ω = f}, by the atom characterization of Local Hardy spaces in a bounded Lipschitz domain, the bound of f→(△)2(Gf) for every f ∈ hrp(Ω) is obtained, where n/(n 1)＜p≤1.     

Continuity of Marcinkiewicz integrals on homogeneous Morrey-Herz spaces

Let μmΩ,b be the higher order commutator generated by Marcinkiewicz integral μΩ and a BMO(Rn) function b(x). In this paper, we will study the continuity ofμΩ and μmΩ,b on homogeneous Morrey-Herz spaces.     

Degenerate principal series and local theta correspondence II

Following our previous paper [LZ] which deals with the groupU(n, n), we study the structure of certain Howe quotients Ω ^p,q and Ω ^p,q (1) which are natural Sp(2n,R) modules arising from the Oscillator representation associated with the dual pair (O(p, q), Sp(2n,R)), by embedding them into the degenerate principal series representations of Sp(2n,R) studied in [L2].     

On the complexity of a single cell in certain arrangements of surfaces related to motion planning

We obtain near-quadratic upper bounds on the maximum combinatorial complexity of a single cell in certain arrangements ofn surfaces in 3-space where the lower bound for this quantity is Ω(n ²) or slightly larger. We prove a theorem that identifies a collection of topological and combinatorial conditions for a set of surface patches in space, which make the complexity of a single cell in an arrangement induced by these surface patches near-quadratic. We apply this result to arrangements related to motion-planning problems of two types of robot systems with three degrees of freedom and also to a special type of arrangements of triangles in space. The complexity of the entire arrangement in each case that we study can be Θ(n ³) in the worst case, and our single-cell bounds are of the formO(n ² α(n)), O(n ² logn), orO(n ² α(n)logn). The only previously known similar bounds are for the considerably simpler arrangements of planes or of spheres in space, where the bounds are Θ(n) and Θ(n ²), respectively. For some of the arrangements that we study we derive near-quadratic-time algorithms to compute a single cell. A preliminary version of this paper has appeared inProc. 7th ACM Symposium on Computational Geometry, North Conway, NH, 1991, pp. 314–323.     

Solutions of elliptic equations involving critical Sobolev exponents with neumann boundary conditions

We consider the problem −Δu=|u| ^p−1u+λu in Ω with on δΩ, where Ω is a bounded domain inR ^N ,p=(N+2)/(N−2) is the critical Sobolev exponent,n the outward pointing normal and λ a constant. Our main result is that if Ω is a ball inR ^N , then for every λ∈R the problem admits infinitely many solutions. Next we prove that for every bounded domain Ω inR ³, symmetric with respect to a plane, there exists a constant μ>0 such that for every λ<μ this problem has at least one non-trivial solution. This work was supported by the Paris VI-Leiden exchange program Supported by the Netherlands organisation for scientific research NWO, under number 611-306-016.     

Energy Equality and Uniqueness of Weak Solutions to MHD Equations in L∞（0, T; L^n（Ω））

In this paper, we study the energy equality and the uniqueness of weak solutions to the MHD equations in the critical space L∞（0, T; L^n（Ω）. We prove that if the velocity u belongs to the critical space L∞（0, T; L^n（Ω）, the energy equality holds. On the basis of the energy equality, we further prove that the weak solution to the MHD equations is unique.     

Cyclotomic and simplicial matroids

We show that two naturally occurring matroids representable over ℚ are equal: thecyclotomic matroid μ_n represented by then ^th roots of unity 1, ζ, ζ², …, ζ^n-1 inside the cyclotomic extension ℚ(ζ), and a direct sum of copies of a certain simplicial matroid, considered originally by Bolker in the context of transportation polytopes. A result of Adin leads to an upper bound for the number of ℚ-bases for ℚ(ζ) among then ^th roots of unity, which is tight if and only ifn has at most two odd prime factors. In addition, we study the Tutte polynomial of μ_n in the case thatn has two prime factors. First author supported by NSF Postdoctoral Fellowship. Second author supported by NSF grant DMS-0245379.     

A direct proof for lower semicontinuity of polyconvex functionals

Lower semicontinuity for polyconvex functionals of the form ∫_Ω g(detDu)dx with respect to sequences of functions fromW ^1,n (Ω;ℝ ⁿ ) which converge inL ¹ (Ωℝ ⁿ ) and are uniformly bounded inW ^1,n−1 (Ω;ℝ ⁿ ), is proved. This was first established in [5] using results from [1] on Cartesian Currents. We give a simple direct proof which does not involve currents. We also show how the method extends to prove natural, essentially optimal, generalizations of these results. Supported by MURST, Gruppo Nazionale 40% Partially supported by Australian Research Council     

Geometric Lower Bounds for Parametric Matroid Optimization

We relate the sequence of minimum bases of a matroid with linearly varying weights to three problems from combinatorial geometry: k -sets, lower envelopes of line segments, and convex polygons in line arrangements. Using these relations we show new lower bounds on the number of base changes in such sequences: Ω(nr ^1/3 ) for a general n -element matroid with rank r , and Ω(mα(n)) for the special case of parametric graph minimum spanning trees. The only previous lower bound was Ω(n log r) for uniform matroids; upper bounds of O(mn ^1/2 ) for arbitrary matroids and O(mn ^1/2 / log ^* n) for uniform matroids were also known. Received November 12, 1996, and in revised form February 19, 1997.     

On proper holomorphic self-maps of generalized complex ellipsoids

The purpose of this paper is to prove that every proper holomorphic self-mapping of a Reinhardt domain Ω in C ⁿ which is a generalization of a complex ellipsoid is biholomorphic. The main novelty of our result is that Ω is a domain in C ⁿ such that it is allowed to have a boundary point at which the Levi determinant has infinite order of vanishing.     

Intersection properties of boxes. Part I: An upper-bound theorem

LetP be a family ofn boxes inR ^d (with edges parallel to the coordinate axes). Fork=0, 1, 2, …, denote byf _k (P) the number of subfamilies ofP of sizek+1 with non-empty intersection. We show that iff _r (P)=0 for somer≦n, then where thef _k (n, d, r) are ceg196rtain definite numbers defined by (3.4) below. The result is best possible for eachk. Fork=1 it was conjectured by G. Kalai (Israel J. Math.48 (1984), 161–174). As an application, we prove a ‘fractional’ Helly theorem for families of boxes inR ^d .     

Decompositions of the Hardy space Hz^1（Ω）

We give a decomposition of the Hardy space Hz^1（Ω） into ＂div-curl＂ quantities for Lipschitz domains in R^n. We also prove a decomposition of Hz^1（Ω） into Jacobians det Du, u ∈ W0^1,2 （Ω,R^2） for Ω in R^2. This partially answers a well-known open problem.     

Comparison theorems for the volume of a complex submanifold of a Kaehler manifold

LetM be a Kaehler manifold of real dimension 2n with holomorphic sectional curvatureK _H≥4λ and antiholomorphic Ricci curvatureρ _A≥(2n−2)λ, andP is a complex hypersurface. We give a bound for the quotient (volume ofP)/(volume ofM) and prove that this bound is attained if and only ifP=C P ⁿ⁻¹(λ) andM=C P ⁿ(λ). Moreover, we give some results on the volume of of tubes aboutP inM. Work partially supported by a DGICYT Grant No. PS87-0115-CO3-01.