Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time

The Fréchet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other, without backtracking. We propose a natural extension of Fréchet distance to more general metric spaces, which requires the leash itself to move continuously over time. For example, for curves in the punctured plane, the leash cannot pass through or jump over the obstacles (“trees”). We describe a polynomial-time algorithm to compute the homotopic Fréchet distance between two given polygonal curves in the plane minus a given set of polygonal obstacles.     

Fréchet versus strongly Fréchet

We construct under [CH] a Tychonoff pseudocompact Fréchet space and a countably compact Hausdorff Fréchet space which are both not strongly Fréchet.     

Double convergence and products of Fréchet spaces

The paper is devoted to convergence of double sequences and its application to products. In a convergence space we recognize three types of double convergences and points, respectively. We give examples and describe their structure and properties. We investigate the relationship between the topological and convergence closure product of two Fréchet spaces. In particular, we give a necessary and sufficient condition for the topological product of two compact Hausdorff Fréchet spaces to be a Fréchet space.     

Computing generalized higher-order Voronoi diagrams on triangulated surfaces

We present an algorithm for computing exact shortest paths, and consequently distance functions, from a generalized source (point, segment, polygonal chain or polygonal region) on a possibly non-convex triangulated polyhedral surface. The algorithm is generalized to the case when a set of generalized sites is considered, providing their distance field that implicitly represents the Voronoi diagram of the sites. Next, we present an algorithm to compute a discrete representation of the distance function and the distance field. Then, by using the discrete distance field, we obtain the Voronoi diagram of a set of generalized sites (points, segments, polygonal chains or polygons) and visualize it on the triangulated surface. We also provide algorithms that, by using the discrete distance functions, provide the closest, furthest and k-order Voronoi diagrams and an approximate 1-Center and 1-Median.     

Streaming Algorithms for Line Simplification

We study the following variant of the well-known line-simplification problem: we are getting a (possibly infinite) sequence of points p ₀,p ₁,p ₂,… in the plane defining a polygonal path, and as we receive the points, we wish to maintain a simplification of the path seen so far. We study this problem in a streaming setting, where we only have a limited amount of storage, so that we cannot store all the points. We analyze the competitive ratio of our algorithms, allowing resource augmentation: we let our algorithm maintain a simplification with 2k (internal) points and compare the error of our simplification to the error of the optimal simplification with k points. We obtain the algorithms with O(1) competitive ratio for three cases: convex paths, where the error is measured using the Hausdorff distance (or Fréchet distance), xy-monotone paths, where the error is measured using the Hausdorff distance (or Fréchet distance), and general paths, where the error is measured using the Fréchet distance. In the first case the algorithm needs O(k) additional storage, and in the latter two cases the algorithm needs O(k ²) additional storage.     

A universal differentiability set in Banach spaces with separable dual

We show that any non-zero Banach space with a separable dual contains a totally disconnected, closed and bounded subset S of Hausdorff dimension 1 such that every Lipschitz function on the space is Fréchet differentiable somewhere in S.     

Fréchet algebras of finite type

The main objects of study in this paper are Fréchet algebras having an Arens Michael representation in which every Banach algebra is finite dimensional. We shall classify these algebras using a theorem which ensures that the image of any continuous linear map of a Fréchet space of finite type (i.e., for which the defining seminorms have a finite dimensional cokernel) into any Fréchet space is in fact closed.This work is part of the research project of the European Research Training Network Analysis and Operators, contract HPRN-CT 2000 00116, funded by the European Commission.     

Productively Fréchet Spaces

We solve the long standing problem of characterizing the class of strongly Fréchet spaces whose product with every strongly Fréchet space is also Fréchet.     

Attainment and (sub)differentiability of the infimal convolution of a function and the square of the norm

Let X be a Banach space whose norm is simultaneously LUR and Gateaux (Fréchet) smooth. Under some assumptions, it is shown that the infimal convolution of a fairly general function on X and the square of the norm is generically strongly attained and hence is Gateaux (Fréchet) differentiable. This contains a result of S. Dutta on distance functions.     

Projectively bounded Fréchet measures

A scalar valued set function on a Cartesian product of -algebras is a Fréchet measure if it is a scalar measure independently in each coordinate. A basic question is considered: is it possible to construct products of Fréchet measures that are analogous to product measures in the classical theory? A Fréchet measure is said to be projectively bounded if it satisfies a Grothendieck type inequality. It is shown that feasibility of products of Fréchet measures is linked to the projective boundedness property. All Fréchet measures in a two dimensional framework are projectively bounded, while there exist Fréchet measures in dimensions greater than two that are projectively unbounded. A basic problem is considered: when is a Fréchet measure projectively bounded? Some characterizations are stated. Applications to harmonic and stochastic analysis are given.

     

Workshop lecture on products of Fréchet spaces

The general question, “When is the product of Fréchet spaces Fréchet?” really depends on the questions of when a product of α₄ Fréchet spaces (also known as strongly Fréchet or countably bisequential spaces) is α₄, and when it is Fréchet. Two subclasses of the class of strongly Fréchet spaces shed much light on these questions. These are the class of α₃ Fréchet spaces and its subclass of ℵ₀-bisequential spaces. The latter is closed under countable products, the former not even under finite products. A number of fundamental results and open problems are recalled, some further highlighting the difference between being α₃ and Fréchet and being ℵ₀-bisequential.     

Reduction of discontinuity for derivations on Frechet algebras

We consider strictly irreducible representations with whichthe discontinuity of a derivation on a (locally multiplicativelyconvex) Fréchet algebra must be associated. Only thosestrictly irreducible representations which are compatible withthe topology of the algebra are considered. The main resultsshow that when consideration is fixed upon each seminorm, theexceptional set of primitive ideals supporting the discontinuitymust be a finite set, with each ideal being the kernel of somefinite-dimensional irreducible representation. This result isthe best possible, as can be seen by considering the radicalFréchet algebra constructed by Charles Read with identityadjoined which has a derivation with separating ideal that isthe entire algebra, and one could take (countable) Fréchetproducts of his counterexample. It is also proved that derivationson commutative Fréchet algebras, the structure spacesof which are compact metric in the weak* topology, have onlyfinitely many such exceptional points overall.     

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.     

Local and global existence and uniqueness results for impulsive functional differential equations with multiple delay

In this paper, we discuss local and global existence and uniqueness results for first-order impulsive functional differential equations with multiple delay. We shall rely on a fixed point theorem of Schaefer and a nonlinear alternative of Leray-Schauder. For the global existence and uniqueness we apply a recent nonlinear alternative of Leray-Schauder type in Fréchet spaces, due to Frigon and Granas [M. Frigon, A. Granas, Résultats de type Leray-Schauder pour des contractions sur des espaces de Fréchet, Ann. Sci. Math. Québec 22 (2) (1998) 161-168].     

On Lipschitz conditions for ordinary differential equations in Fréchet spaces

We will give an existence and uniqueness theorem for ordinary differential equations in Fréchet spaces using Lipschitz conditions formulated with a generalized distance and row-finite matrices.     

A “retraction” method for planning the motion of a disc

A new approach to certain motion-planning problems in robotics is introduced. This approach is based on the use of a generalized Voronoi diagram, and reduces the search for a collision-free continuous motion to a search for a connected path along the edges of such a diagram. This approach yields an O(n log n) algorithm for planning an obstacle-avoiding motion of a single circular disc amid polygonal obstacles. Later papers will show that extensions of the approach can solve other motion-planning problems, including those of moving a straight line segment or several coordinated discs in the plane amid polygonal obstacles.     

基于遗传算法重建多个散射体的组合Newton法

本文研究由单个入射声波或电磁波及其远场数据反演多个柔性散射体边界的逆散射问题.通过建立边界到边界总场的非线性算子及其n6chet导数,本文首先给出了基于单层位势的组合Newton法.将组合Newton法转化为泛响优化问题,从而获得了该方法重建单个散射体的收敛性分析.然后,基于遗传算法和正则化参数选取的模型函数方法,给出...     

Fixed point theory for admissible multimaps defined on closed subsets of Fréchet spaces

This paper presents new fixed point results for a general class of maps defined on Fréchet spaces. Our results in particular apply to Kakutani, acyclic, O'Neill, approximable, admissible with respect to Gorniewicz and maps.