Open questions concerning Weiszfeld's algorithm for the Fermat-Weber location problem

The Fermat—Weber location problem is to find a point in ⁿ that minimizes the sum of the weighted Euclidean distances fromm given points in ⁿ . A popular iterative solution method for this problem was first introduced by Weiszfeld in 1937. In 1973 Kuhn claimed that if them given points are not collinear then for all but a denumerable number of starting points the sequence of iterates generated by Weiszfeld's scheme converges to the unique optimal solution. We demonstrate that Kuhn's convergence theorem is not always correct. We then conjecture that if this algorithm is initiated at the affine subspace spanned by them given points, the convergence is ensured for all but a denumerable number of starting points.     

The Fermat—Weber location problem revisited

The Fermat—Weber location problem requires finding a point in ^N that minimizes the sum of weighted Euclidean distances tom given points. A one-point iterative method was first introduced by Weiszfeld in 1937 to solve this problem. Since then several research articles have been published on the method and generalizations thereof. Global convergence of Weiszfeld's algorithm was proven in a seminal paper by Kuhn in 1973. However, since them given points are singular points of the iteration functions, convergence is conditional on none of the iterates coinciding with one of the given points. In addressing this problem, Kuhn concluded that whenever them given points are not collinear, Weiszfeld's algorithm will converge to the unique optimal solution except for a denumerable set of starting points. As late as 1989, Chandrasekaran and Tamir demonstrated with counter-examples that convergence may not occur for continuous sets of starting points when the given points are contained in an affine subspace of ^N . We resolve this open question by proving that Weiszfeld's algorithm converges to the unique optimal solution for all but a denumerable set of starting points if, and only if, the convex hull of the given points is of dimensionN.     

Analytic Solutions of L∞ Optimal Control Problems for the Wave Equation

There are very few results about analytic solutions of problems of optimal control with minimal L norm. In this paper, we consider such a problem for the wave equation, where the derivative of the state is controlled at both boundaries. We start in the zero position and consider a problem of exact control, that is, we want to reach a given terminal state in a given finite time. Our aim is to find a control with minimal L norm that steers the system to the target.We give the analytic solution for certain classes of target points, for example, target points that are given by constant functions. For such targets with zero velocity, the analytic solution has been given by Bennighof and Boucher in Ref. 1.     

Some bounds for the deviation and interpolation points in Chebyshev approximation

Some bounds are given for the deviation and interpolation points of a functionf based on bounds forf ⁽ⁿ⁺²⁾/f ⁽ⁿ⁺¹⁾. These bounds are in terms of the deviation and interpolation points ofe ^vx , –1 x 1, wherev is a parameter. The behavior of these points asv is also discussed.The results of this paper are contained in the second author's Master's thesis submitted to the University of Wyoming in May 1969.     

Saddle points and overdetermined problems for the Helmholtz equation

In a seminal 1971 paper, James Serrin showed that the only open, smoothly bounded domain in ⁿ on which the positive Dirichlet eigenfunction of the Laplacian has constant (nonzero) normal derivative on the boundary, is then-dimensional ball. The positivity of the eigenfunction is crucial to his proof. To date it is an open conjecture that the same result is true for Dirichlet eigenvalues other than the least. We show that for simply connected, plane domains, the absence of saddle points is a condition sufficient to validate this conjecture. This condition is also sufficient to prove Schiffer's conjecture: the only simply connected planar domain, on the boundary of which a nonconstant Neumann eigenfunction of the Laplacian can take constant value, is the disc.     

Pseudo Jordan domains and reflecting Brownian motions

Summary The manifold metric between two points in a planar domain is the minimum of the lengths of piecewiseC ¹ curves in the domain connecting these two points. We define a bounded simply connected planar region to be a pseudo Jordan domain if its boundary under the manifold metric is topologically homeomorphic to the unit circle. It is shown that reflecting Brownian motionX on a pseudo Jordan domain can be constructed starting at all points except those in a boundary subset of capacity zero.X has the expected Skorokhod decomposition under a condition which is satisfied when G has finite 1-dimensional lower Minkowski content.     

Approximation of the efficient point set by perturbation of the ordering cone

A vector optimization problem is given by a feasible setZ ⁿ , a vector-valued objective functionf: ^{n l} , and an ordering coneC ^l . We perturb the ordering cone in such a way that the weakly efficient points of the perturbed vector optimization problem given byZ, f, and the perturbed cone are efficient points of the original problem. Especially this means that scalarization methods, which compute in general only weakly efficient points, determine efficient points of the original problem, when they were applied to the perturbed problem.It turns out that the efficient points are the limits of weakly efficient points of the perturbed problems, letting the perturbation tend to zero. On the basis of this, a reference point algorithm is formulated. Finally, we apply this algorithm to a structural optimization problem.     

Improved difference schemes for the Dirichlet problem of Poisson's equation in the neighbourhood of corners

Summary The standard 5-point difference scheme for the model problem u=f on a special polygonal domain with given boundary values is modified at a few points in the neighbourhood of the corners in such a way that the order of convergence at interior points is the same as in the case of a smooth boundary. As a side result improved error bounds for the usual method in the neighbourhood of corners are given.     

Gitterpunkte in Lemniskatenscheiben

Let G (R) denote the number of lattice points (,) **Z² in the domain B(R) bounded by the lemniscate (x²+y²)²=2R² (x²–y²) and put P(R)=G(R)-R²(R² being the area of B(R)). The purpose of this paper is to determine the order of magnitude of P(R) for large R by proving the asymptotic relation (3). An analogous result is given for the eight curve x⁴=R² (x²–y²).     

Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points

This paper presents an algorithm and its probabilistic analysis for constructing the convex hull ofm given points in ?ⁿ then-dimensional Euclidean space. The algorithm under consideration combines the Gift-Wrapping concept with the so-called Throw-Away Principle (introduced by Akl and Toussaint [1] and later by Devroye [10]) for nonextremal points. The latter principle had been used for a convex-hull-construction algorithm in R² and for its probabilistic analysis in a recent paper by Borgwardtet al. [5]. There, the considerations remained much simpler, because in ?² the construction of the convex hull essentially requires recognition of the extremal points and of their order only. In this paper the Simplex method is used to organize a walk over the surface of the convex hull. During this walk all facets are discovered. Under the condition of general position this information is sufficient, because the whole face lattice can simply be deduced when the set of facets is available. Exploiting the advantages of the revised Simplex method reduces the update effort to ann ×n matrix and the number of calculated quotients for the pivot search to the points which are not thrown away. For this algorithm a probabilistic analysis can be carried out. We assume that ourm random points are distributed identically, independently, and symmetrically under rotations in Rⁿ. Then the calculation of the expected effort becomes possible for a whole parametrical class of distributions over the unit ball. The results mean a progress in three directions:

a parametrization of the expected effort can be given;

the dependency onn— the dimension of the space—can be evaluated;

the additional work of preprocessing for detecting the vertices can be avoided without losing its advantages.

     

About the Decay of Vorticity in a Two-dimensional Incompressible Viscous Fluid

The main purpose of this article is to investigate the behavior of the vorticity in a two dimensional incompressible viscous medium. We give bounds for the maximal amount of vorticity which can be concentrated in a domain of a given size. In order to obtain bounds we compare the vorticity equation to the heat equation in ²     

The problem of recovering the permittivity coefficient from the modulus of the scattered electromagnetic field

Under consideration is the stationary system of equations of electrodynamics relating to a nonmagnetic nonconducting medium. We study the problem of recovering the permittivity coefficient ε from given vectors of electric or magnetic intensities of the electromagnetic field. It is assumed that the field is generated by a point impulsive dipole located at some point y. It is also assumed that the permittivity differs from a given constant ε₀ only inside some compact domain Ω ? R³ with smooth boundary S. To recover ε inside Ω, we use the information on a solution to the corresponding direct problem for the system of equations of electrodynamics on the whole boundary of Ω for all frequencies from some fixed frequency ω ₀ on and for all y ∈ S. The asymptotics of a solution to the direct problem for large frequencies is studied and it is demonstrated that this information allows us to reduce the initial problem to the well-known inverse kinematic problem of recovering the refraction index inside Ω with given travel times of electromagnetic waves between two arbitrary points on the boundary of Ω. This allows us to state uniqueness theorem for solutions to the problem in question and opens up a way of its constructive solution.     

Algorithms for approximate calculation of the minimum of a convex function from its values

The paper deals with a numerical minimization problem for a convex function defined on a convexn-dimensional domain and continuous (but not necessarily smooth). The values of the function can be calculated at any given point. It is required to find the minimum with desired accuracy. A new algorithm for solving this problem is presented, whose computational complexity asn is considerably less than that of similar algorithms known to the author. In fact, the complexity is improved fromCn ⁷ ln²(n+1) [4] toCn ² ln(n+1).Translated fromMatematicheskie Zametki, Vol. 59, No. 1, pp. 95–102, January, 1996.     

On the stationary,compressible and incompressible navier-stokes equations

Summary In this paper we study the system (1.1), (1.3) which describes the stationary motion of a given amount of a compressible heat conducting, viscous fluid in a bounded domain of Rⁿ, n2, and we consider the incompressible limit of the solutions of that system of equations (for barotropic flows) as the Mach number becomes small.     

Intrinsic third derivatives for Plateau's problem and the Morse inequalities for disc minimal surfaces in ℝ3

Summary A simply branched minimal surface in ³ cannot be a non-degenerate critical point of Dirichlet's energy since the Hessian always has a kernel. However such minimal surface can be non-degenerate in another sense introduced earlier by R. Böhme and the author. Such surfaces arise as the zeros of a vector field on the space of all disc surfaces spanning a fixed contour. In this paper we show that the winding number of this vector field about such a surface is ±2 ^p , wherep is the number of branch points. As a consequence we derive the Morse inequalities for disc minimal surfaces in ³, thereby completing the program initiated by Morse, Tompkins, and Courant. Finally, this result implies that certain contours in ⁴ arbitrarily close to the given contour must span at least 2 ^p disc minimal surfaces.     

Determination of efficient solutions for point-objective locational decision problems

In this paper we study the point-objective problem of locating in ² a facility serving a finite number of customers to minimize the travel time, or the distance, to each customer.Travel times, or distances, are measured by going in the directions of some given vectors which means that, under some conditions, are evaluated by a norm function. An algorithm is proposed to find all the quasi-efficient points and all the efficient points (alternately or strictly), for any given set of travelling directions. Consequently, the problem of efficiency is addressed in a general framework.     

Some characterizing properties of the simplex

We shall prove that a convex body in ^d (d2) is a simplex if, and only if, each of its Steiner symmetrals is a convex double cone over the symmetrization space or, equivalently, has exactly two extreme points outside of this hyperplane. In [3] it is shown that every Steiner symmetral of an arbitrary d-simplex is such a double cone, more precisely a bipyramid. Therefore our main aim is to prove that a convex body which is not a simplex has Steiner symmetrals with more than two extreme points not in the symmetrization space. Some equivalent properties of simplices will also be given.     

Generation of all integer points for given sets of linear inequalities

We propose to give a computationally feasible procedure for the generation of all the integer points satisfying a given set of inequalities. Five different systems of inequalities will be considered. In order to generate all of these integer points, one requires a particular set of integer points, called fundamental points, and a set of linearly independent vectors with integer components. The number of these fundamental points is given by a simple formula. We show how to generate the fundamental points and the required vectors. We give an application concerning the localization of the integer optimum of a linear objective function subject to constraints which geometrically define a cone or a parallelotope.This paper was presented at the 7th Mathematical Programming Symposium, 1970, The Hague, The Netherlands, under the title Some linear inequalities in Z ⁿ .     

Algebraic methods in discrete analogs of the Kakeya problem

We prove the joints conjecture, showing that for any N lines in R³, there are at most points at which 3 lines intersect non-coplanarly. We also prove a conjecture of Bourgain showing that given N² lines in R³ so that no N lines lie in the same plane and so that each line intersects a set P of points in at least N points then the cardinality of the set of points is Ω(N³). Both our proofs are adaptations of Dvir's argument for the finite field Kakeya problem.