Diameter,width, closest line pair,and parametric searching

We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved solutions for them. We obtain, for any fixed ε>0, anO(n ^1+ε) algorithm for computing the diameter of a point set in 3-space, anO(^8/5+ε) algorithm for computing the width of such a set, and onO(n ^8/5+ε) algorithm for computing the closest pair in a set ofn lines in space. All these algorithms are deterministic. Work by Bernard Chazelle was supported by NSF Grant CCR-90-02352. Work by Herbert Edelsbrunner was supported by NSF Grant CCR-89-21421. Work by Leonidas Guibas and Micha Sharir was supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Micha Sharir was also supported by ONR Grant N00014-90-J-1284, by NSF Grant CCR-89-01484, and by grants from the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

Analytic solutions of the Borel problem

LetF ⊂ ℂ be a dense-in-itself set that has a nonempty connected interior and contains the origin, and let be the space of infinitely differentiable complex-valued functions onF. For some classes of such setsF, we prove that for an arbitrary sequence of complex numbers there exists a functionf ε withf ⁽ⁿ⁾(0)=d _n,n=0, 1, 2, ..., and study the analyticity properties off. The functionf is constructed in the form of various function series, namely, a power series, a series of simple fractions, and an exponential series. Analytic solutions of the multidimensional Borel problem are also considered. Translated fromMatematicheskie Zametki, Vol. 67, No. 4, pp. 525–538, April, 2000.     

Rational solutions of the graphsack problem

A graphsack problem is a certain binary linear optimization problem with applications in optimal network design. From there a rational graphsack problem is derived by allowing the variables to vary continuously between 0 and 1. In this paper we deal with rational graphsack problems. First we develop the concept of compressed solutions and the concept of augmenting cuts. Making use of these concepts a very simple optimality criterion is derived. Finally an efficient algorithm solving rational graphsack problems is given which is polynomially bounded in time and which is closely related to the simplex algorithm.     

On solutions to the Goldshtik problem

The Goldshtik model for separated flows in an incompressible fluid is considered. A solution to this two-dimensional problem of mathematical physics for a finite domain is found with a finite element method. Estimates of the differential operator are obtained. A result on the number of solutions to the Goldshtik problem is obtained using a variational method.     

Wavelet solutions for the Dirichlet problem

Summary. A modified classical penalty method for solving a Dirichlet boundary value problem is presented. This new fictitious domain penalty method eliminates the traditional need of generating a complex computation grid in the case of irregular domains. It is based on the fact that one can expand the boundary measure under the chosen basis which leads to a fast, approximate calculation of boundary integral. The compact support and orthonormality of the basis are essential for representing the boundary measure numerically, and therefore for implementing this methodology. Received June 3, 1992 / Revised version received November 8, 1993     

Multiplicity of solutions for the bounce problem

The bounce trajectories in a convex set which assume assigned positions in two fixed time instants are sought. Sufficient conditions in order to obtain the existence of infinitely many bounce trajectories are found.     

Fundamental solutions of the eight queens problem

Previous algorithms presented to solve the eight queens problem have generated the set of all solutions. Many of these solutions are identical after applying sequences of rotations and reflections. In this paper we present a simple, clear, efficient algorithm to generate a set of fundamental (or distinct) solutions to the problem.     

Compactness of solutions to the Yamabe problem

We establish compactness of solutions to the Yamabe problem on any smooth compact connected Riemannian manifold (not conformally diffeomorphic to standard spheres) of dimension n?7 as well as on any manifold of dimension n?8 under some additional hypothesis. To cite this article: Y.Y. Li, L. Zhang, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Entire solutions of the abstract cauchy problem

We introduce a family of operators that we will callentire C-groups, and apply them to the first and second order abstract Cauchy problem, for a large class of linear operators on a Banach space. This produces unique solutions, for all initial data in a large (often dense) set, eachof which extends to an entire function, with continuous dependence on the initial data. Applications include the backward heat equation and the Cauchy problem for the Laplace equation.     

A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes

For a given pair of finite point setsP andQ in some Euclidean space we consider two problems: Problem 1 of finding the minimum Euclidean norm point in the convex hull ofP and Problem 2 of finding a minimum Euclidean distance pair of points in the convex hulls ofP andQ. We propose a finite recursive algorithm for these problems. The algorithm is not based on the simplicial decomposition of convex sets and does not require to solve systems of linear equations.     

Structure of regular solutions of Faddeev equations near the pair impact point

We study the two-and three-dimensional Faddeev equations for a three-particle system with central or S-wave pair interactions. The regular solutions of such equations are represented as infinite series in integer powers of the distance between two particles and the sought functions of the other three-particle coordinates. Constructing such functions reduces to solving algebraic recurrence relations. We derive the boundary conditions at the pair impact point for the regular solutions of the Faddeev equations. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 156, No. 1, pp. 112–130, July, 2008.     

Sub-core solutions of the problem of strong implementation

The problem of strong implementation is to determine which social choice correspondences (SCC) can be obtained as the strong equilibrium correspondence of a game form. We introduce the notion of the nucleus of an effectivity function. Under certain conditions, it yields the smallest implementable SCC having that effectivity function. We contrast it with the core, which yields the largest implementable SCC (as shown by Moulin and Peleg), and argue that the smaller solution should be preferred when available. Another result is that the known necessary conditions for implementability are not sufficient, except in the case of (at most) 3 alternatives.     

The Nash problem for a toric pair and the minimal log-discrepancy

This Note formulates the Nash problem for a pair consisting of a toric variety and an invariant ideal and gives an affirmative answer to the problem. We also prove that the minimal log-discrepancy is computed by a divisor corresponding to a Nash component, if the minimal log-discrepancy is finite. On the other hand there exists a Nash component such that the corresponding divisor has negative log-discrepancy, if the minimal log-discrepancy is ?∞.     

Functional solutions of the problem of discontinuity disintegration

A definition is given of functional solutions of the problem of discontinuity disintegration, and an example of such a solution is presented for the isoentropic system of gas dynamics. Translated fromMatematicheskie Zametki, Vol. 63, No. 2, pp. 280–288, February, 1998.