Piecewise linear paths among convex obstacles

Let ℬ be a set ofn arbitrary (possibly intersecting) convex obstacles in ℝ ^d . It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path consisting ofO(n ^{(d−1)[d/2+1]}) segments. The bound cannot be improved below Ω(n ^d ); thus, in ℝ³, the answer is betweenn ³ andn ⁴. For open disjoint convex obstacles, a Θ(n) bound is proved. By a well-known reduction, the general case result also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles. Asymptotically tight bounds and efficient algorithms are given in the planar case. This research was supported by The Netherlands' Organization for Scientific Research (NWO) and partially by the ESPRIT III Basic Research Action 6546 (PROMotion). J. M. acknowledges support by a Humboldt Research Fellowship. Part of this research was done while he visited Utrecht University.     

Near optimal bounds for the Erdős distinct distances problem in high dimensions

We show that the number of distinct distances in a set of n points in ℝ ^d is Ω(n ^{2/d − 2 / d(d + 2)}), d ≥ 3. Erdős’ conjecture is Ω(n ^2/d ).     

On visibility and covering by convex sets

A setX⊆ℝ ^d isn-convex if among anyn of its points there exist two such that the segment connecting them is contained inX. Perles and Shelah have shown that any closed (n+1)-convex set in the plane is the union of at mostn ⁶ convex sets. We improve their bound to 18n ³, and show a lower bound of order Ω(n ²). We also show that ifX⊆ℝ² is ann-convex set such that its complement has λ one-point path-connectivity components, λ<∞, thenX is the union ofO(n ⁴+n ²λ) convex sets. Two other results onn-convex sets are stated in the introduction (Corollary 1.2 and Proposition 1.4). Research supported by Charles University grants GAUK 99/158 and 99/159, and by U.S.-Czechoslovak Science and Technology Program Grant No. 94051. Part of the work by J. Matoušek was done during the author’s visits at Tel Aviv University and The Hebrew University of Jerusalem. Part of the work by P. Valtr was done during his visit at the University of Cambridge supported by EC Network DIMANET/PECO Contract No. ERBCIPDCT 94-0623.     

Counting triangle crossings and halving planes

Every collection oft≥2n ² triangles with a total ofn vertices in ℝ³ has Ω(t ⁴/n ⁶) crossing pairs. This implies that one of their edges meets Ω(t ³/n ⁶) of the triangles. From this it follows thatn points in ℝ³ have onlyO(n ^8/3) halving planes. The research of H. Edelsbrunner was supported by the National Science Foundation under Grant CCR-8921421 and under an Alan T. Waterman award, Grant CCR-9118874. Any opinions, findings and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the view of the National Science Foundation.     

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.     

Properties of the Flows Generated by Stochastic Equations with Reflection

We consider the properties of a random set ϕ _t (ℝ ₊ ^d ), where ϕ _t (x) is a solution of a stochastic differential equation in ℝ ₊ ^d with normal reflection from the boundary that starts from a point x. We characterize inner and boundary points of the set ϕ _t (ℝ ₊ ^d ) and prove that the Hausdorff dimension of the boundary ∂ϕ _t (ℝ ₊ ^d ) does not exceed d − 1. __________ Translated from Ukrains'kyi Matematychnyi Zhurnal, Vol. 57, No. 8, pp. 1069 – 1078, August, 2005.     

The Helmholtz decomposition of weightedLq-spaces for Muckenhoupt weights

We consider weights of Muckenhoupt classA _q, 1<q<∞. For a bounded Lipschitz domain Ω⊂ℝⁿ we prove a compact embedding and a Poincaré inequality in weighted Sobolev spaces. These technical tools allow us to solve the weak Neumann problem for the Laplace equation in weighted spaces on ℝⁿ, ℝⁿ ₊, on bounded and on exterior domains Ω with boundary of classC ¹, which will yield the Helmholtz decomposition ofL _ω ^q(Ω)ⁿ for general ω∈A _q. This is done by transferring the method of Simader and Sohr [4] to the weighted case. Our result generalizes a result of Farwig and Sohr [2] where the Helmholtz decomposition ofL _ω ^p(Ω)ⁿ is proved for an exterior domain and weights of Muckenhoupt class without singularities or degeneracies in a neighbourhood of ϖΩ.

---

Sunto In questo lavoro consideriamo dei pesi della classe di MuckenhouptA _q, 1<q<∞. Per un dominio limitato lipschitziano Ω⊂ℝⁿ, dimostriamo una immersione compatta ed una disuguaglianza di Poincaré in spazi di Sobolev con peso. Questa tecnica ci consente di risolvere il problema debole di Neumann per l’equazione di Laplace in spazi pesati in ℝⁿ, ℝⁿ ₊ in domini limitati ed in domini esterni con frontiera di classeC ¹, che conduce alla decomposizione di Helmholtz diL _ω ^q(Ω)ⁿ per un qualsiasi ω∈A _q. Il risultato è ottenuto trasferendo il metodo di Simader e Sohr [4] al caso pesato. Quello qui presente estende un risultato di Farwig e Sohr [2] dove la decomposizione di Helmholtz diL _ω ^q(Ω)ⁿ è dimostrata per domini esterni e pesi della classe di Muckenhoupt privi di singolarità in un intorno di ϖΩ.

     

Uniform harmonic approximation with continuous extension to the boundary

Let Ω be an open set in ℝ ⁿ andE be a relatively closed subset of Ω. Further, letC _e(E) be the collection of real-valued continuous functions onE which extend continuously to the closure ofE in ℝ ⁿ . We characterize those pairs (Ω,E) which have the following property: every function inC _e(E) which is harmonic onE ⁰ can be uniformly approximated onE by functions which are harmonic on Ω and whose restrictions toE belong toC _e(E).     

Area,coarea, and approximation in <Emphasis Type="Italic">W</Emphasis><Superscript>1,1</Superscript>

Let Ω⊂ℝ ⁿ be an arbitrary open set. We characterize the space W ^1,1 _loc(Ω) using variants of the classical area and coarea formulas. We use these characterizations to obtain a norm approximation and trace theorems for functions in the space W ^1,1(ℝ ⁿ ).     

Surjective partial differential operators on real analytic functions defined on open convex sets

Let P(D) be a partial differential operator with constant coefficients which is surjective on the space A(Ω) of real analytic functions on a covex open set Ω⊂ℝ ⁿ . Let L(P _m ) denote the localizations at ∞ (in the sense of H?rmander) of the principal part P _m . Then Q(x+iτN)≠ 0 for (x,τ)∈ℝ ⁿ ×(ℝ\{ 0}) for any Q∈L(P _m ) if N is a normal to δΩ which is noncharacteristic for Q. Under additional assumptions this implies that P _m must be locally hyperbolic. Received: 24 January 2000     

On the stability of solutions to quadratic programming problems

We consider the parametric programming problem (Q _p ) of minimizing the quadratic function f(x,p):=x ^T Ax+b ^T x subject to the constraint Cx≤d, where x∈ℝ ⁿ , A∈ℝ ^n×n , b∈ℝ ⁿ , C∈ℝ ^m×n , d∈ℝ ^m , and p:=(A,b,C,d) is the parameter. Here, the matrix A is not assumed to be positive semidefinite. The set of the global minimizers and the set of the local minimizers to (Q _p ) are denoted by M(p) and M ^loc (p), respectively. It is proved that if the point-to-set mapping M ^loc (·) is lower semicontinuous at p then M ^loc (p) is a nonempty set which consists of at most ? _m,n points, where ? _m,n = is the maximal cardinality of the antichains of distinct subsets of {1,2,...,m} which have at most n elements. It is proved also that the lower semicontinuity of M(·) at p implies that M(p) is a singleton. Under some regularity assumption, these necessary conditions become the sufficient ones. Received: November 5, 1997 / Accepted: September 12, 2000?Published online November 17, 2000     

Bounding the number of connected components of a real algebraic set

For every polynomial mapf=(f ₁,…,f _k): ℝ ⁿ →ℝ ^k , we consider the number of connected components of its zero set,B(Z _f) and two natural “measures of the complexity off,” that is the triple(n, k, d), d being equal to max(degree off _i), and thek-tuple (Δ₁,...,Δ₄), Δ _k being the Newton polyhedron off _i respectively. Our aim is to boundB(Z _f) by recursive functions of these measures of complexity. In particular, with respect to (n, k, d) we shall improve the well-known Milnor-Thom’s bound μ _d (n)=d(2d−1) ⁿ⁻¹. Considered as a polynomial ind, μ _d (n) has leading coefficient equal to 2 ⁿ⁻¹. We obtain a bound depending onn, d, andk such that ifn is sufficiently larger thank, then it improves μ _d (n) for everyd. In particular, it is asymptotically equal to 1/2(k+1)n ^k−1 dⁿ, ifk is fixed andn tends to infinity. The two bounds are obtained by a similar technique involving a slight modification of Milnor-Thom's argument, Smith's theory, and information about the sum of Betti numbers of complex complete intersections.     

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).     

Voronoi diagrams of random lines and flats

It is proved that, for any fixedd ≽ 3 and 0 ≤k ≤ d - 1, the expected combinatorial complexity of the Euclidean Voronoi diagram ofn random &-flats drawn independently from the uniform distribution onk-flats intersecting the unit ball in ℝ^d is Ξ(n ^d/(d-k)) asn → ∞. A by-product of the proof is a density transformation for integrating over sets ofd + 1k-flats in ℝ^d     

A note on certain square functions on product spaces

We study certain square functions on product spaces Rn × Rm, whose integral kernels are obtained from kernels which are homogeneous in each factor Rn and Rm and locally in L(log L) away from Rn × {0} and {0} × Rm by means of polynomial distortions in the radial variable. As a model case, we obtain that the Marcinkiewicz integral operator is bounded on Lp(Rn × Rm)(P > 1) for Ω∈ e Llog L(Sn-1 × Sm-1) satisfying the cancellation condition.     

Stabbing Simplices by Points and Flats

The following result was proved by Bárány in 1982: For every d≥1, there exists c _d >0 such that for every n-point set S in ℝ ^d , there is a point p∈ℝ ^d contained in at least c _d n ^d+1−O(n ^d ) of the d-dimensional simplices spanned by S. We investigate the largest possible value of c _d . It was known that c _d ≤1/(2 ^d (d+1)!) (this estimate actually holds for every point set S). We construct sets showing that c _d ≤(d+1)^−(d+1), and we conjecture that this estimate is tight. The best known lower bound, due to Wagner, is c _d ≥γ _d :=(d ²+1)/((d+1)!(d+1) ^d+1); in his method, p can be chosen as any centerpoint of S. We construct n-point sets with a centerpoint that is contained in no more than γ _d n ^d+1+O(n ^d ) simplices spanned by S, thus showing that the approach using an arbitrary centerpoint cannot be further improved.     

Multiwavelet packets and frame packets ofL 2(ℝ d )

The orthonormal basis generated by a wavelet ofL ²(ℝ) has poor frequency localization. To overcome this disadvantage Coifman, Meyer, and Wickerhauser constructed wavelet packets. We extend this concept to the higher dimensions where we consider arbitrary dilation matrices. The resulting basis ofL ²(ℝ ^d ) is called the multiwavelet packet basis. The concept of wavelet frame packet is also generalized to this setting. Further, we show how to construct various orthonormal bases ofL ²(ℝ ^d ) from the multiwavelet packets.     

A Bichromatic Incidence Bound and an Application

We prove a new, tight upper bound on the number of incidences between points and hyperplanes in Euclidean d-space. Given n points, of which k are colored red, there are O _d (m ^2/3 k ^2/3 n ^(d−2)/3+kn ^d−2+m) incidences between the k red points and m hyperplanes spanned by all n points provided that m=Ω(n ^d−2). For the monochromatic case k=n, this was proved by Agarwal and Aronov (Discrete Comput. Geom. 7(4):359–369, 1992).     

Partial regularity for weak solutions of a nonlinear elliptic equation

For scalar non-linear elliptic equations, stationary solutions are defined to be critical points of a functional with respect to the variations of the domain. We consideru a weak positive solution of −Δu=u ^α in -Δu=u ^α in Ω ⊂ ℝ ⁿ , which is stationary. We prove that the Hausdorff dimension of the singular set ofu is less thann−2α+1/α−1, if α≥n+2/n−2.     

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.