Entropy,Approximation Quantities and the Asymptotics of the Modulus of Continuity

The paper deals with the approximation of bounded real functions f on a compact metric space (X, d) by so-called controllable step functions in continuation of [Ri/Ste]. These step functions are connected with controllable coverings, that are finite coverings of compact metric spaces by subsets whose sizes fulfil a uniformity condition depending on the entropy numbers ε_n(X) of the space X. We show that a strong form of local finiteness holds for these coverings on compact metric subspaces of IR^m and S^m. This leads to a Bernstein type theorem if the space is of finite convex information. In this case the corresponding approximation numbers ε_n(f) have the same asymptotics its ω(f, ε_n(X)) for f ε C(X). Finally, the results concerning functions f ε M(X) and f ε C(X) are transferred to operators with values in M(X) and C(X), respectively.     

Planar rectilinear shortest path computation using corridors

The rectilinear shortest path problem can be stated as follows: given a set of m non-intersecting simple polygonal obstacles in the plane, find a shortest L₁-metric (rectilinear) path from a point s to a point t that avoids all the obstacles. The path can touch an obstacle but does not cross it. This paper presents an algorithm with time complexity O(n+m(lgn)^3/2), which is close to the known lower bound of Ω(n+mlgm) for finding such a path. Here, n is the number of vertices of all the obstacles together.     

Low distortion euclidean embeddings of trees

We consider the problem of embedding a certain finite metric space to the Euclidean space, trying to keep the bi-Lipschitz constant as small as possible. We introduce the notationc ₂(X, d) for the least distortion with which the metric space (X, d) may be embedded in a Euclidean space. It is known that if (X, d) is a metric space withn points, thenc ₂(X, d)≤0(logn) and the bound is tight. LetT be a tree withn vertices, andd be the metric induced by it. We show thatc ₂(T, d)≤0(log logn), that is we provide an embeddingf of its vertices to the Euclidean space, such thatd(x, y)≤‖f(x)−f(y) ‖≤c log lognd(x, y) for some constantc. Supported in part by grants from the Israeli Academy of Sciences and the US-Israel Binational Science Foundation. Supported in part by NSF under grants CCR-9215293 and by DIMACS, which is supported by NSF grant STC-91-19999 and by the New Jersey Commission on Science and Technology.     

Vafa-Witten bound on the complex projective space

We prove that the largest first eigenvalue of the Dirac operator among all Hermitian metrics on the complex projective space of odd dimension m, larger than the Fubini-Study metric is bounded by (2m(m+1))^1/2. Mathematics Subject Classification (2000): 53C27, 58J50, 58J60.     

Lipschitz selections of set-valued mappings and Helly’s theorem

We prove a Helly-type theorem for the family of all m-dimensional convex compact subsets of a Banach space X. The result is formulated in terms of Lipschitz selections of set-valued mappings from a metric space (M, ρ) into this family. Let M be finite and let F be such a mapping satisfying the following condition: for every subset M′ ⊂ M consisting of at most 2^m+1 points, the restriction F|_M′ of F to M′ has a selection f_M′ (i. e., f_M′(x) ∈ F(x) for all x ∈ M′) satisfying the Lipschitz condition ‖ƒ_M′(x) − ƒ_M′(y)‖_X ≤ ρ(x, y), x, y ∈ M′. Then F has a Lipschitz selection ƒ: M → X such that ‖ƒ(x) − ƒ(y)‖_X ≤ γρ(x,y), x, y ∈ M where γ is a constant depending only on m and the cardinality of M. We prove that in general, the upper bound of the number of points in M′, 2^m+1, is sharp. If dim X = 2, then the result is true for arbitrary (not necessarily finite) metric space. We apply this result to Whitney’s extension problem for spaces of smooth functions. In particular, we obtain a constructive necessary and sufficient condition for a function defined on a closed subset of R ² to be the restriction of a function from the Sobolev space W _∞ ² (R ²).A similar result is proved for the space of functions on R ² satisfying the Zygmund condition.     

Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs

The main question discussed in this paper is how well a finite metric space of size n can be embedded into a graph with certain topological restrictions. The existing constructions of graph spanners imply that any n -point metric space can be represented by a (weighted) graph with n vertices and n ^{1 +O(1/r)} edges, with distances distorted by at most r . We show that this tradeoff between the number of edges and the distortion cannot be improved, and that it holds in a much more general setting. The main technical lemma claims that the metric space induced by an unweighted graph H of girth g cannot be embedded in a graph G (even if it is weighted) of smaller Euler characteristic, with distortion less than g/4 - 3/2 . In the special case when |V(G)| =|V(H)| and G has strictly less edges than H , an improved bound of g/3 - 1 is shown. In addition, we discuss the case χ(G) < χ(H) - 1 , as well as some interesting higher-dimensional analogues. The proofs employ basic techniques of algebraic topology. Received September 26, 1995, and in revised form March 18, 1996.     

Embedding metric spaces in the rectilinear plane: A six-point criterion

We show that a metric space embeds in the rectilinear plane (i.e., isL ¹-embeddable in ℝ²) if and only if every subspace with five or six points does. A simple construction shows that for higher dimensionsk of the host rectilinear space the numberc(k) of points that need to be tested grows at least quadratically withk, thus disproving a conjecture of Seth and Jerome Malitz.     

Self-packing of centrally symmetric convex bodies in ℝ2

LetB be a compact convex body symmetric around0 in ℝ² which has nonempty interior, i.e., the unit ball of a two-dimensional Minkowski space. The self-packing radiusρ(m,B) is the smallestt such thatt B can be packed withm translates of the interior ofB. Form≤6 we show that the self-packing radiusρ(m,B)=1+2/α(m,B) whereα(m,B) is the Minkowski length of the side of the largest equilateralm-gon inscribed inB (measured in the Minkowski metric determined byB). We showρ(6,B)=ρ(7,B)=3 for allB, and determine most of the largest and smallest values ofρ(m,B) form≤7. For allm we have

Fréchet Spaces of Holomorphic Functions without Copies of l1

Let X be a Banach space. Let H_w*(X*) the Fréchet space whose elements are the holomorphic functions defined on X* whose restrictions to each multiple mB(X*), m = 1,2, …, of the closed unit ball B(X*) of X* are continuous for the weak-star topology. A fundamental system of norms for this space is the supremum of the absolute value of each element of H_w*(X*) in mB(X*), m = 1,2,…. In this paper we construct the bidual of l₁ when this space contains no copy of l¹. We also show that if X is an Asplund space, then H_w*(X*) can be represented as the projective limit of a sequence of Banach spaces that are Asplund.     

Ray Shooting Amidst Convex Polygons in 2D

We consider the problem of ray shooting in a two-dimensional scene consisting ofmconvex polygons with a total ofnedges. We present a data structure that requiresO(mn log m) space and preprocessing time and that answers a ray shooting query inO(log² m log² n) time. If the polygons are pairwise disjoint, the space and preprocessing time can be improved toO((m²+n)log m) andO((m²+n log n)log m), respectively. Our algorithm also works for a collection of disjoint simple polygons. We also show that if we allow onlyO(n) space, a ray shooting query among a collection of disjoint simple polygons can be answered in timeO(m/[formula]¹⁺ log² n) time, for any >0.     

Topological Complexity of Motion Planning

   Abstract. In this paper we study a notion of topological complexity TC (X) for the motion planning problem. TC (X) is a number which measures discontinuity of the process of motion planning in the configuration space X . More precisely, TC (X) is the minimal number k such that there are k different "motion planning rules," each defined on an open subset of X× X , so that each rule is continuous in the source and target configurations. We use methods of algebraic topology (the Lusternik—Schnirelman theory) to study the topological complexity TC (X) . We give an upper bound for TC (X) (in terms of the dimension of the configuration space X ) and also a lower bound (in terms of the structure of the cohomology algebra of X ). We explicitly compute the topological complexity of motion planning for a number of configuration spaces: spheres, two-dimensional surfaces, products of spheres. In particular, we completely calculate the topological complexity of the problem of motion planning for a robot arm in the absence of obstacles.     

Minimum dissection of a rectilinear polygon with arbitrary holes into rectangles

In this paper, the problem of dissecting a plane rectilinear polygon with arbitrary (possibly, degenerate) holes into a minimum number of rectangles is shown to be solvable inO(n ^3/2 logn) time. This fact disproves a famous assertion about the NP-hardness of the minimum rectangular dissection problem for rectilinear polygons with point holes.     

Topological Complexity of Motion Planning

Abstract. In this paper we study a notion of topological complexity TC (X) for the motion planning problem. TC (X) is a number which measures discontinuity of the process of motion planning in the configuration space X . More precisely, TC (X) is the minimal number k such that there are k different "motion planning rules," each defined on an open subset of X× X , so that each rule is continuous in the source and target configurations. We use methods of algebraic topology (the Lusternik—Schnirelman theory) to study the topological complexity TC (X) . We give an upper bound for TC (X) (in terms of the dimension of the configuration space X ) and also a lower bound (in terms of the structure of the cohomology algebra of X ). We explicitly compute the topological complexity of motion planning for a number of configuration spaces: spheres, two-dimensional surfaces, products of spheres. In particular, we completely calculate the topological complexity of the problem of motion planning for a robot arm in the absence of obstacles.     

The book crossing number of a graph

Let G be a graph on n vertices and m edges. The book crossing number of G is defined as the minimum number of edge crossings when the vertices of G are placed on the spine of a k-page book and edges are drawn on pages, such that each edge is contained by one page. Our main results are two polynomial time algorithms to generate near optimal drawing of G on books. The first algorithm give an O(log² n) times optimal solution, on small number of pages, under some restrictions. This algorithm also gives rise to the first polynomial time algorithm for approximating the rectilinear crossing number so that the coordinates of vertices in the plane are small integers, thus resolving a recent open question concerning the rectilinear crossing number. Moreover, using this algorithm we improve the best known upper bounds on the rectilinear crossing number. The second algorithm generates a drawing of G with O(m²/k²) crossings on k pages. This is within a constant multiplicative factor from our general lower bound of Ω(m³/n²k²), provided that m = Ψ(n²). © 1996 John Wiley & Sons, Inc.     

Computing minimum-area rectilinear convex hull and L-shape

We study the problems of computing two non-convex enclosing shapes with the minimum area; the L-shape and the rectilinear convex hull. Given a set of n points in the plane, we find an L-shape enclosing the points or a rectilinear convex hull of the point set with minimum area over all orientations. We show that the minimum enclosing shapes for fixed orientations change combinatorially at most O(n) times while rotating the coordinate system. Based on this, we propose efficient algorithms that compute both shapes with the minimum area over all orientations. The algorithms provide an efficient way of maintaining the set of extremal points, or the staircase, while rotating the coordinate system, and compute both minimum enclosing shapes in O(n²) time and O(n) space. We also show that the time complexity of maintaining the staircase can be improved if we use more space.     

Retracts, fixed point property and existence of periodic points

Let X be a metric space, f ∈ C⁰( X), andV ⊂X. The set-trajectory ( V, f( V), …,f ⁿ (V)) is investigated and some conditions for f to have periodic points with given periods are obtained.     

连续自映射拓扑压的两个注记

令T:X→ X是紧度量空间(X,d)上的连续映射.该文给出了T的拓扑压和T在非游荡集上的限制的拓扑压相等的不依赖于变分原理的一个直接证明.同时,还讨论了半共轭的两个系统的拓扑压之间的关系,证明了拓扑压在一致有限对一条件下是半共轭不变量.     

A NON-LINEAR ℓ 1 PROBLEM

Abstract

In this note we consider a non-linear problem posed to the author in a private communication with Per Enflo: If a normed space X contains a non-linear ? ₁ ⁽ⁿ⁾-cube (where n ≥ 2 is a natural number) does it necessarily contain a linear isometric copy of ? ₁ ⁽ⁿ⁾?

We exhibit a strong regularity property of non-linear ? ₁ ⁽ⁿ⁾ cubes and apply it to obtain an affirmative answer to Enflo's problem in the setting X = l _∞ ^(m) that, moreover, coincides precisely with well known linear theory.     

The Moduli Space of Points in the Boundary of Complex Hyperbolic Space

We consider the space M(n,m)\mathcal{M}(n,m) of ordered m-tuples of distinct points in the boundary of complex hyperbolic n-space, H_\mathbbCⁿ\mathbf{H}_{\mathbb{C}}^{n}, up to its holomorphic isometry group PU(n,1). An important problem in complex hyperbolic geometry is to construct and describe the moduli space for M(n,m)\mathcal{M}(n,m). In particular, this is motivated by the study of the deformation space of complex hyperbolic groups generated by loxodromic elements. In the present paper, we give the complete solution to this problem.