How to Cut Pseudoparabolas into Segments

Let Γ be a collection of unbounded x -monotone Jordan arcs intersecting at most twice each other, which we call pseudoparabolas, since two axis parallel parabolas intersect at most twice. We investigate how to cut pseudoparabolas into the minimum number of curve segments so that each pair of segments intersect at most once. We give an Ω( n ^4/3 ) lower bound and O(n ^5/3 ) upper bound on the number of cuts. We give the same bounds for an arrangement of circles. Applying the upper bound, we give an O(n ^23/12 ) bound on the complexity of a level in an arrangement of pseudoparabolas, and an O(n ^11/6 ) bound on the complexity of a combinatorially concave chain of pseudoparabolas. We also give some upper bounds on the number of transitions of the minimum weight matroid base when the weight of each element changes as a quadratic function of a single parameter. Received January 17, 1996, and in revised form November 7, 1996.     

AnO(n logn) algorithm for computing the link center of a simple polygon

We present an algorithm that determines the link center of a simplen-vertex polygonP inO(n logn) time. The link center of a simple polygon is the set of pointsx insideP at which the maximal link-distance fromx to any other point inP is minimized. The link distance between two pointsx andy insideP is defined to be the smallest number of straight edges in a polygonal path insideP connectingx andy. Using our algorithm we also obtain anO(n logn)-time solution to the problem of determining the link radius ofP. The link radius ofP is the maximum link distance from a point in the link center to any vertex ofP. Both results are improvements over theO(n ²) bounds previously established for these problems. The research of J.-R. Sack was supported by the Natural Sciences and Engineering Research Council of Canada.     

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.     

An additive divisor problem with a growing number of factors

Let τk(n) be the number of representations ofn as the product ofk positive factors, τ(n)=τ(n). The asymptotics of Σ _n≤x τ _k (n)τ(n+1) for 80k ¹⁰ (lnlnx)³≤lnx is shown to be uniform with respect tok. Translated fromMatematicheskie Zametki, Vol. 61, No. 3, pp. 391–406, March, 1997. Translated by N. K. Kulman     

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.     

L2(Rn) boundedness for commutators of oscillatory singular integral operators

The commutators of oscillatory singular integral operators with homogeneous kernel \fracW(x)| x |ⁿ \frac{{\Omega (x)}}{{\left| x \right|^n }} are studied, where Ω is homogeneous of degree zero, has mean value zero on the unit sphere. It is proved that Ω∈L (logL)^K+1(S^n-1) is a sufficient condition under which the k-th order commutator is bounded on L²(Rⁿ).     

On the covering multiplicity of lattices

Let the lattice Λ have covering radiusR, so that closed balls of radiusR around the lattice points just cover the space. The covering multiplicityCM(Λ) is the maximal number of times the interiors of these balls overlap. We show that the least possible covering multiplicity for ann-dimensional lattice isn ifn≤8, and conjecture that it exceedsn in all other cases. We determine the covering multiplicity of the Leech lattice and of the latticesI _n, A_n, D_n, E_n and their duals for small values ofn. Although it appears thatCM(I _n)=2 ⁿ⁻¹ ifn≤33, asn → ∞ we haveCM(I _n)∼2.089... ⁿ . The results have application to numerical integration.     

Simultaneous approximation of periodic continuous functions and their derivatives

LetR _n(f; x) be a trigonometric polynomial of ordern satisfying Eqs. (1.1) and (1.2). The object of this note is to obtain sufficient conditions in order that thepth derivative ofR _n(f, x) converges uniformly tof ^(p)(x) on the real line. The sufficient conditions turns out to bef ^(p)(x) ∈ Lipα, α>0 with the restrictions of Eq. (1.3). The author acknowledges financial support for this work from the University of Alberta, Post Doctoral Fellowship 1966–67. The author is extremely grateful to the referee for pointing out some valuable results and suggestions.     

Extreme Jensen measures

Let Ω be an open subset of R ^d , d≥2, and let x∈Ω. A Jensen measure for x on Ω is a Borel probability measure μ, supported on a compact subset of Ω, such that ∫u  dμ≤u(x) for every superharmonic function u on Ω. Denote by J _x (Ω) the family of Jensen measures for x on Ω. We present two characterizations of ext(J _x (Ω)), the set of extreme elements of J _x (Ω). The first is in terms of finely harmonic measures, and the second as limits of harmonic measures on decreasing sequences of domains. This allows us to relax the local boundedness condition in a previous result of B. Cole and T. Ransford, Jensen measures and harmonic measures, J. Reine Angew. Math. 541 (2001), 29–53. As an application, we give an improvement of a result by Khabibullin on the question of whether, given a complex sequence {α _n } _n=1 ^∞ and a continuous function , there exists an entire function f≢0 satisfying f(α _n )=0 for all n, and |f(z)|≤M(z) for all z∈C.     

D p spaces on bounded symmetric domains ofC n

In this paper, the spaceD ^p(Ω) of functions holomorphic on bounded symmetric domain ofC ⁿ is defined. We prove thatH ^p(Ω)⊂D ^p(Ω) if 0<p≤2, andD ^p(Ω)⊂H ^p(Ω) ifp≥2, and both the inclusions are proper. Further, we find that some theorems onH ^p(Ω) can be extended to a wider classD ^p(Ω) for 0<p≤2.     

Application of Hilbert＇s Projective Metric on Symmetric Cones

Let Ω be a symmetric cone. In this note, we introduce Hilbert＇s projective metric on Ω in terms of Jordan algebras and we apply it to prove that, given a linear invertible transformation g such that g（Ω） = Ω and a real number p, ｜p｜ 〉 1, there exists a unique element x ∈ Ω satisfying g（x） = x^p.     

On order preserving contractions

Let (Ω,Σ,μ) be a measure space and letP be an operator onL ₂(Ω,Σ,μ) with ‖P‖≦1,Pf≧0 a.e. wheneverf≧0. If the subspaceK is defined byK={x| ||P ⁿ x||=||P ^*n x||=||x||,n=1,2,...} thenK=L ₂(Ω,Σ₁,μ), where Σ₁ ⊂ Σ and onK the operatorP is “essentially” a measure preserving transformation. Thus the eigenvalues ofP of modulus one, form a group under multiplication. This last result was proved by Rota for finiteμ here finiteness is not assumed) and is a generalization of a theorem of Frobenius and Perron on positive matrices. The research reported in this document has been sponsored in part by Air Force Office of Scientific Research, OAR through the European Office, Aerospace Research, United States Air Force.     

RETRACTED ARTICLE: Some applications of BP-theorem in approximation theory

In this paper we apply Bishop-Phelps property to show that if X is a Banach space and G X is the maximal subspace so that G⊥ = {x* ∈ X*|x*(y) = 0; y∈ G} is an L-summand in X*, then L1(Ω,G) is contained in a maximal proximinal subspace of L1(Ω,X).     

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.     

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.     

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.     

Sausages are good packings

LetB ^d be thed-dimensional unit ball and, for an integern, letC _n ={x ¹,...,x ⁿ } be a packing set forB ^d , i.e.,|x ⁱ −x ^j |≥2, 1≤i<j≤n. We show that for every a dimensiond(ρ) exists such that, ford≥d(ρ),V(conv(C _n )+ρB ^d )≥V(conv(S _n )+ρB ^d ), whereS _n is a “sausage” arrangement ofn balls, holds. This gives considerable improvement to Fejes Tóth's “sausage” conjecture in high dimensions. Further, we prove that, for every convex bodyK and ρ<1/32d ⁻²,V(conv(C _n )+ρK)≥V(conv(S _n )+ρK), whereC _n is a packing set with respect toK andS _n is a minimal “sausage” arrangement ofK, holds.     

Cbmo estimates for Marcinkiewicz integrals on homogeneous Morrey-Herz spaces

The boundedness of the commutator μΩ,b generalized by Marcinkiewicz integral μΩ and a function b(x) ∈ CBMOq(Rn) on homogeneous Morrey-Herz spaces is established.     

Arrangements of segments that share endpoints: Single face results

We provide new combinatorial bounds on the complexity of a face in an arrangement of segments in the plane. In particular, we show that the complexity of a single face in an arrangement ofn line segments determined byh endpoints isO(h logh). While the previous upper bound,O(nα(n)), is tight for segments with distinct endpoints, it is far from being optimal whenn=Ω(h ²). Our results show that, in a sense, the fundamental combinatorial complexity of a face arises not as a result of the number ofsegments, but rather as a result of the number ofendpoints. The research of E. M. Arkin was partially supported by NSF Grants ECSE-8857642 and CCR-9204585. K. Kedem's research was partially supported by AFOSR Grant AFOSR-91-0328. The research of J. S. B. Mitchell was partially supported by a grant from Boeing Computer Services, Hughes Research Laboratories, AFOSR Grant AFOSR-91-0328, and by NSF Grants ECSE-8857642 and CCR-9204585.     

Some results related to interpolation on hardy spaces of regular martingales

Let (Ω,F, P) be a probability space and {F _n}_n≥0 a regular increasing sequence of sub-σ-fields ofF. LetH ₁(Ω) be the usual Hardy space ofF _n-martingales. We show that the couple (H ₁(Ω),L _∞(Ω)) is a partial retract of (L ₁(Ω),L _∞(Ω)). It is also proved that (L _p(Ω),BMO(Ω)) is a partial retract of (L _p(Ω),L _∞(Ω)) for all 1<p<∞.