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.     

The Besov Space B^{{0,1}}_{1} on Domains

Let Ω be a bounded Lipschitz domain. Define B ^0,1 _{1, r} (Ω) = {f∈L ¹ (Ω): there is an F∈B ^0,1 ₁ (ℝ ⁿ ) such that F|_Ω = f} and B ^0,1 _{1 z} (Ω) = {f∈B ^0,1 ₁ (ℝ ⁿ ) : f = 0 on ℝ ⁿ \}. In this paper, the authors establish the atomic decompositions of these spaces. As by-products, the authors obtained the regularity on these spaces of the solutions to the Dirichlet problem and the Neumann problem of the Laplace equation of ℝ ⁿ ₊. Received June 8, 2000, Accepted October 24, 2000     

Raising Roofs,Crashing Cycles,and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions

The straight skeleton of a polygon is a variant of the medial axis introduced by Aichholzer et al., defined by a shrinking process in which each edge of the polygon moves inward at a fixed rate. We construct the straight skeleton of an n -gon with r reflex vertices in time O(n ^1+ε + n ^8/11+ε r ^9/11+ε ) , for any fixed ε >0 , improving the previous best upper bound of O(nr log n) . Our algorithm simulates the sequence of collisions between edges and vertices during the shrinking process, using a technique of Eppstein for maintaining extrema of binary functions to reduce the problem of finding successive interactions to two dynamic range query problems: (1) maintain a changing set of triangles in R ³ and answer queries asking which triangle is first hit by a query ray, and (2) maintain a changing set of rays in R ³ and answer queries asking for the lowest intersection of any ray with a query triangle. We also exploit a novel characterization of the straight skeleton as a lower envelope of triangles in R ³ . The same time bounds apply to constructing non-self-intersecting offset curves with mitered or beveled corners, and similar methods extend to other problems of simulating collisions and other pairwise interactions among sets of moving objects. Received July 1, 1998, and in revised form March 29, 1999.     

Existence and multiplicity of solutions for a nonlinear Neumann problem

We consider a Neumann problem of the type -εΔu+F ^′(u(x))=0 in an open bounded subset Ω of R ⁿ , where F is a real function which has exactly k maximum points. Using Morse theory we find that, for ε suitably small, there are at least 2k nontrivial solutions of the problem and we give some qualitative information about them. Received: October 30, 1999 Published online: December 19, 2001     

Kinetic Connectivity for Unit Disks

We describe a kinetic data structure (KDS) that maintains the connected components of the union of a set of unit-radius disks moving in the plane. We assume that the motion of each disk can be specified by a low-degree algebraic trajectory; this trajectory, however, can be modified in an on-line fashion. While the disks move continuously, their connectivity changes at discrete times. Our main result is an O(n) space data structure that takes O(log n\slash \kern -1pt log log n) time per connectivity query of the form ``are disks A and B in the same connected component?' A straightforward approach based on dynamically maintaining the overlap graph requires Ω (n ² ) space. Our data structure requires only linear space and must deal with O(n ^{2 + ε} ) updates in the worst case, each requiring O(log ² n) amortized time, for any ε>0 . This number of updates is close to optimal, since a set of n moving unit disks can undergo Ω (n ² ) connectivity changes. Received September 20, 2000, and in revised form January 19, 2001. Online publication April 6, 2001.     

Nice Point Sets Can Have Nasty Delaunay Triangulations

   Abstract. We consider the complexity of Delaunay triangulations of sets of points in R ³ under certain practical geometric constraints. The spread of a set of points is the ratio between the longest and shortest pairwise distances. We show that in the worst case, the Delaunay triangulation of n points in R ³ with spread Δ has complexity Ω(min{ Δ³, nΔ, n² }) and O(min{ Δ⁴, n ² }). For the case

The Forest Hiding Problem

Let Ω be a disk of radius R in the plane. A set F of unit disks contained in Ω forms a maximal packing if the unit disks are pairwise interior-disjoint and the set is maximal, i.e., it is not possible to add another disk to F while maintaining the packing property. A point p is hidden within the “forest” defined by F if any ray with apex p intersects some disk of F, that is, a person standing at p can hide without being seen from outside the forest. We show that if the radius R of Ω is large enough, one can find a hidden point for any maximal packing of unit disks in Ω. This proves a conjecture of Joseph Mitchell. We also present an O(n ^5/2log n)-time algorithm that, given a forest with n (not necessarily congruent) disks, computes the boundary illumination map of all disks in the forest.     

Nearly flat almost monotone measures are big pieces of lipschitz graphs

A concentrated (ξ, m) almost monotone measure inR ⁿ is a Radon measure Φ satisfying the two following conditions: (1) Θ ^m (Φ,x)≥1 for every x ∈spt (Φ) and (2) for everyx ∈R ⁿ the ratioexp [ξ(r)]r^−mΦ(B(x,r)) is increasing as a function of r>0. Here ξ is an increasing function such thatlim _r→0-ξ(r)=0. We prove that there is a relatively open dense setReg (Φ) ∋spt (Φ) such that at each x∈Reg(Φ) the support of Φ has the following regularity property: given ε>0 and λ>0 there is an m dimensional spaceW ⊂R ⁿ and a λ-Lipschitz function f from x+W into x+W^‖ so that (100-ε)% ofspt(Φ) ∩B (x, r) coincides with the graph of f, at some scale r>0 depending on x, ε, and λ.     

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.     

Partial regularity of mass-minimizing rectifiable sections

Let B be a fiber bundle with compact fiber F over a compact Riemannian n-manifold M ⁿ. There is a natural Riemannian metric on the total space B consistent with the metric on M. With respect to that metric, the volume of a rectifiable section σ: M → B is the mass of the image σ(M) as a rectifiable n-current in B. Theorem 1. For any homology class of sections of B, there is a mass-minimizing rectifiable current T representing that homology class which is the graph of a C¹ section on an open dense subset of M. Mathematics Subject Classifications (2000): 49F20, 49F22, 49F10, 58A25, 53C42, 53C65.     

Classification of the isomorphic types of martingale-H 1 spaces

LetF _n be an increasing sequence of finite fields on a probability space (Ω,F _n,P) whereF denotes the σ-algebra generated by ∪F _n. ThenF _n is isomorphic to one of the following spaces:H ¹(δ), ΣH _n ¹ ,l ^l.     

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.     

Distribution of points on spheres and approximation by zonotopes

It is proved that if we approximate the Euclidean ballB ⁿ in the Hausdorff distance up toɛ by a Minkowski sum ofN segments, then the smallest possibleN is equal (up to a possible logarithmic factor) toc(n)ε ^{−2(n−1)/(n+2)}. A similar result is proved ifB ⁿ is replaced by a general zonoid inR ⁿ .     

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.

     

Strikte Konvexität für Variationsprobleme auf demn-dimensionalen Torus

We consider a variational problem with an integrandF:R ⁿ ×R×R ⁿ →R that isZ-periodic in the firstn+1 variables and satisfies certain growth-conditions. By a recent result of Moser, there exist for every α∈R ⁿ minimal solutionsu:R ⁿ →R minimising ƒF(x, u(x), u _x (x)) dx with respect to compactly supported variations ofu and such that sup |u(x)-αx|<∞. Given such a minimal solutionu we define the average action (whereB _r is ther-ball around 0∈R ⁿ ) and show thatM(α) is indeed independent of the minimal solutionu satisfying sup |u(x)-αx|<∞. We prove that this average actionM(α) is strictly convex in α.      

Sharp Estimates in Bergman and Besov Spaces on Bounded Symmetric Domains

Sharp estimates of the point-evaluation functional in weighted Bergman spaces L ^p _a (Ω, dν _α) and for the point-evaluation derivalive functional in Besov spaces B ^p (Ω) are obtained for bounded symmetric domains Ω in ℂ ⁿ . Received October 25, 1999, Accepted December 6, 2000     

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.     

Sobolev functions whose inner trace at the boundary is zero

Let Ω⊂R ⁿ be an arbitrary open set. In this paper it is shown that if a Sobolev functionf∈W ^1,p (Ω) possesses a zero trace (in the sense of Lebesgue points) on ϖΩ, thenf is weakly zero on ϖΩ in the sense thatf∈W ₀ ^1,p (Ω).     

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.