Extreme points of the distance function on convex surfaces

We first see that, in the sense of Baire categories, many convex surfaces have quite large cut loci and infinitely many relative maxima of the distance function from a point. Then we find that, on any convex surface, all these extreme points lie on a single subtree of the cut locus, with at most three endpoints. Finally, we confirm (both in the sense of measure and in the sense of Baire categories) Steinhaus' conjecture that ``almost all" points admit a single farthest point on the surface.

     

Voronoi diagrams for convex polygon-offset distance functions

In this paper we develop the concept of a convex polygon-offset distance function. Using offset as a notion of distance, we show how to compute the corresponding nearest- and furthest-site Voronoi diagrams of point sites in the plane. We provide near-optimal deterministic O (n (log n + log ² m) + m) -time algorithms, where n is the number of points and m is the complexity of the underlying polygon, for computing compact representations of both diagrams. Received January 8, 1999, and in revised form January 5, 2000, and June 12, 2000. Online publication December 4, 2000.     

On delaunay oriented matroids for convex distance functions

For any finite point setS inE ^d, an oriented matroid DOM (S) can be defined in terms of howS is partitioned by Euclidean hyperspheres. This oriented matroid is related to the Delaunay triangulation ofS and is realizable, because of thelifting property of Delaunay triangulations. We prove that the same construction of aDelaunay oriented matroid can be performed with respect to any smooth, strictly convex distance function in the planeE ² (Theorem 3.5). For these distances, the existence of a Delaunay oriented matroid cannot follow from a lifting property, because Delaunay triangulations might be nonregular (Theorem 4.2(i). This is related to the fact that the Delaunay oriented matroid can be nonrealizable (Theorem 4.2(ii). This research was partially supported by the Spanish Grant DGICyT PB 92/0498-C02 and the David and Lucile Packard Foundation.     

Contraction of convex surfaces by nonsmooth functions of curvature

We consider the motion of convex surfaces with normal speed given by arbitrary strictly monotone, homogeneous degree one functions of the principal curvatures (with no further smoothness assumptions). We prove that such processes deform arbitrary uniformly convex initial surfaces to points in finite time, with spherical limiting shape. This result was known previously only for smooth speeds. The crucial new ingredient in the argument, used to prove convergence of the rescaled surfaces to a sphere without requiring smoothness of the speed, is a surprising hidden divergence form structure in the evolution of certain curvature quantities.     

Steepest descent curves of convex functions on surfaces of constant curvature

Let S be a complete surface of constant curvature K = ±1, i.e., S ² or л ², and Ω ? S a bounded convex subset. If S = S ², assume also diameter(Ω) < π/2. It is proved that the length of any steepest descent curve of a quasi-convex function in Ω is less than or equal to the perimeter of Ω. This upper bound is actually proved for the class of G-curves, a family of curves that naturally includes all steepest descent curves. In case S = S ², the existence of G-curves, whose length is equal to the perimeter of their convex hull, is also proved, showing that the above estimate is indeed optimal. The results generalize theorems by Manselli and Pucci on steepest descent curves in the Euclidean plane.     

Typical convex curves on convex surfaces

In the sense of Baire categories, most convex curves on a smooth twodimensional closed convex surface are smooth. Moreover, if the set of all closed geodesics has empty interior in the space of all convex curves, then most convex curves are strictly convex.This paper was written during the author's visit at Western Washington University, whose substantial support is acknowledged.     

Convex sub-differential sum rule via convex semi-closed functions with applications in convex programming

This paper deals with some basic notions of convex analysis and convex optimization via convex semi-closed functions. A decoupling-type result and also a sandwich theorem are proved. As a consequence of the sandwich theorem, we get a convex sub-differential sum rule and two separation results. Finally, the derived convex sub-differential sum rule is applied to solving the convex programming problem.     

Subgradient of distance functions with applications to Lipschitzian stability

The paper is devoted to studying generalized differential properties of distance functions that play a remarkable role in variational analysis, optimization, and their applications. The main object under consideration is the distance function of two variables in Banach spaces that signifies the distance from a point to a moving set. We derive various relationships between Fréchet-type subgradients and limiting (basic and singular) subgradients of this distance function and corresponding generalized normals to sets and coderivatives of set-valued mappings. These relationships are essentially different depending on whether or not the reference point belongs to the graph of the involved set-valued mapping. Our major results are new even for subdifferentiation of the standard distance function signifying the distance between a point and a fixed set in finite-dimensional spaces. The subdifferential results obtained are applied to deriving efficient dual-space conditions for the local Lipschitz continuity of distance functions generated by set-valued mappings, in particular, by those arising in parametric constrained optimization. Dedicated to Terry Rockafellar in honor of his 70th birthday. This research was partially supported by the National Science Foundation under grant DMS-0304989 and by the Australian Research Council under grant DP-0451158.     

Variational convergence for vector-valued functions and its applications to convex multiobjective optimization

The aim of this work is to study a notion of variational convergence for vector-valued functions. We show that it is suitable for obtaining existence and stability results in convex multiobjective optimization. We obtain various of properties of the variational convergence. We characterize it via the set convergence of epigraphs, coepigraphs, level sets, and some infima. We also characterize it by means of two metrics. We compare it with other notions of convergence for vector-valued functions from the literature and we show that it is more general than most of them. For obtaining the existence and stability results we employ an asymptotic method that has shown to be very useful in optimization theory. In this method we couple the variational convergence with notions of asymptotic analysis (asymptotic cones and functions).     

Properties of functions generalized convex with respect to a WT-system

Continuity and convergence properties of functions, generalized convex with respect to a continuous weak Tchebysheff system, are investigated. It is shown that, under certain non-degeneracy assumptions on the weak Tchebysheff system, every function in its generalized convex cone is continuous, and pointwise convergent sequences of generalized convex functions are uniformly convergent on compact subsets of the domain. Further, it is proved that, with respect to a continuous Tchebysheff system, L_p-convergence to a continuous function, pointwise convergence and uniform convergence of a sequence of generalized convex functions are equivalent on compact subsets of the domain.     

Hessian measures of semi-convex functions and applications to support measures of convex bodies

This paper originates from the investigation of support measures of convex bodies (sets of positive reach), which form a central subject in convex geometry and also represent an important tool in related fields. We show that these measures are absolutely continuous with respect to Hausdorff measures of appropriate dimensions, and we determine the Radon-Nikodym derivatives explicitly on sets of σ-finite Hausdorff measure. The results which we obtain in the setting of the theory of convex bodies (sets of positive reach) are achieved as applications of various new results on Hessian measures of convex (semi-convex) functions. Among these are a Crofton formula, results on the absolute continuity of Hessian measures, and a duality theorem which relates the Hessian measures of a convex function to those of the conjugate function. In particular, it turns out that curvature and surface area measures of a convex body K are the Hessian measures of special functions, namely the distance function and the support function of K. Received: 15 July 1999     

Bending of convex surfaces

A survey of results on bending of nonregular convex surfaces is presented.Translated from Itogi Nauki i Tekhniki. Problemy Geometrii, Vol. 10, pp. 193–224, 1978.