On the performance of peeling algorithms

The peeling of a d-dimensional set of points is usually performed with successive calls to a convex hull algorithm; the optimal worst-case convex hull algorithm, known to have an O(n^˙ Log (n)) execution time, may give an O(n^˙n^˙ Log (n)) to peel all the set; an O(n^˙n) convex hull algorithm, m being the number of extremal points, is shown to peel every set with an O(n-n) time, and proved to be optimal; an implementation of this algorithm is given for planar sets and spatial sets, but the latter give only an approximate O(n^˙n) performance.     

Piecewise linear paths among convex obstacles

Let ℬ be a set ofn arbitrary (possibly intersecting) convex obstacles in ℝ ^d . It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path consisting ofO(n ^{(d−1)[d/2+1]}) segments. The bound cannot be improved below Ω(n ^d ); thus, in ℝ³, the answer is betweenn ³ andn ⁴. For open disjoint convex obstacles, a Θ(n) bound is proved. By a well-known reduction, the general case result also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles. Asymptotically tight bounds and efficient algorithms are given in the planar case. This research was supported by The Netherlands' Organization for Scientific Research (NWO) and partially by the ESPRIT III Basic Research Action 6546 (PROMotion). J. M. acknowledges support by a Humboldt Research Fellowship. Part of this research was done while he visited Utrecht University.     

Properties of P-sets and trapped compact convex sets

New properties of P-sets, which constitute a large class of convex compact sets in ? ⁿ that contains all convex polyhedra and strictly convex compact sets, are obtained. It is shown that the intersection of a P-set with an affine subspace is continuous in the Hausdorff metric. In this theorem, no assumption of interior nonemptiness is made, unlike in other known intersection continuity theorems for set-valued maps. It is also shown that if the graph of a set-valued map is a P-set, then this map is continuous on its entire effective set rather than only on the interior of this set. Properties of the so-called trapped sets are also studied; well-known Jung’s theorem on the existence of a minimal ball containing a given compact set in ? ⁿ is generalized. As is known, any compact set contains n + 1 (or fewer) points such that any translation by a nonzero vector takes at least one of them outside the minimal ball. This means that any compact set is trapped in the minimal ball. Compact sets trapped in any convex compact sets, rather than only in norm bodies, are considered. It is shown that, for any compact set A trapped in a P-set M ? ? ⁿ , there exists a set A ⁰ ? A trapped in M and containing at most 2n elements. An example of a convex compact set M ? ? ⁿ for which such a finite set A ⁰ ? A does not exist is given.     

A geometric inequality and the complexity of computing volume

The volume of the convex hull of anym points of ann-dimensional ball with volumeV is at mostV·m/2 ⁿ . This implies that no polynomial time algorithm can compute the volume of a convex set (given by an oracle) with less than exponential relative error. A lower bound on the complexity of computing width can also be deduced.Dedicated to my teacher Kõváry Károly     

Linear Optimization Queries

Let Γ₀ be a set of n halfspaces in E^d (where the dimension d is fixed) and let m be a parameter, n ≤ m ≤ n^d/2. We show that Γ₀ can be preprocessed in time and space O(m^1+δ) (for any fixed δ > 0) so that given a vector c E^d and another set Γ_q of additional halfspaces, the function c · x can be optimized over the intersection of the halfspaces of Γ₀ Γ_q in time O((n/m^1/d/2 + |Γ_q|)log^4d+3n). The algorithm uses a multidimensional version of Megiddo′s parametric search technique and recent results on halfspace range reporting. Applications include an improved algorithm for computing the extreme points of an n-point set P in E^d, improved output-sensitive computation of convex hulls and Voronoi diagrams, and a Monte-Carlo algorithm for estimating the volume of a convex polyhedron given by the set of its vertices (in a fixed dimension).     

Small Grid Embeddings of 3-Polytopes

We introduce an algorithm that embeds a given 3-connected planar graph as a convex 3-polytope with integer coordinates. The size of the coordinates is bounded by O(2^7.55n )=O(188 ⁿ ). If the graph contains a triangle we can bound the integer coordinates by O(2^4.82n ). If the graph contains a quadrilateral we can bound the integer coordinates by O(2^5.46n ). The crucial part of the algorithm is to find a convex plane embedding whose edges can be weighted such that the sum of the weighted edges, seen as vectors, cancel at every point. It is well known that this can be guaranteed for the interior vertices by applying a technique of Tutte. We show how to extend Tutte’s ideas to construct a plane embedding where the weighted vector sums cancel also on the vertices of the boundary face.     

Extreme points for convex mappings ofB n

We exhibit a collection of extreme points of the family of normalized convex mappings of the open unit ball of ℂ ⁿ forn≥2. These extreme points are defined in terms of the extreme points of a closed ball in the Banach space of homogeneous polynomials of degree 2 in ℂ ⁿ⁻¹, which are fully classified. Two examples are given to show that there are more convex mappings than those contained in the closed convex hull of the set of extreme points here exhibited.     

Necessary optimality conditions for a class of nonsmooth vector optimization

The Kuhn-Tucker type necessary conditions of weak efficiency are given for the problem of minimizing a vector function whose each component is the sum of a differentiable function and a convex function, subject to a set of differentiable nonlinear inequalities on a convex subset C of ℝ ⁿ , under the conditions similar to the Abadie constraint qualification, or the Kuhn-Tucker constraint qualification, or the Arrow-Hurwicz-Uzawa constraint qualification. Supported by the National Natural Science Foundation of China (No. 70671064, No. 60673177), the Province Natural Science Foundation of Zhejiang (No.Y7080184) and the Education Department Foundation of Zhejiang Province (No. 20070306).     

Complexity of convex optimization using geometry-based measures and a reference point

Our concern lies in solving the following convex optimization problem:where P is a closed convex subset of the n-dimensional vector space X. We bound the complexity of computing an almost-optimal solution of G_P in terms of natural geometry-based measures of the feasible region and the level-set of almost-optimal solutions, relative to a given reference point x^r that might be close to the feasible region and / or the almost-optimal level set. This contrasts with other complexity bounds for convex optimization that rely on data-based condition numbers or algebraic measures, and that do not take into account any a priori reference point information. Mathematics Subject Classification (2000):90C, 90C05, 90C60This research has been partially supported through the Singapore-MIT Alliance. Portions of this research were undertaken when the author was a Visiting Scientist at Delft University of Technology.Received: 1, October 2001     

The nonlinear complementarity problem with applications,part 1

The main result in this paper is an existence and uniqueness theorem for the following nonlinear complementarity problem: Given a mapping from then-dimensional Euclidean spaceE ⁿ into itself, find a nonnegative vector inE ⁿ whose image, under the given mapping, is also nonnegative, the two vectors being orthogonal to each other. It is shown that the above problem has a unique solution if the given mapping is continuous and strongly monotone on the nonnegative orthantE ₊ ⁿ ofE ⁿ . It is also shown that a sufficient condition for a differentiable mapping to be strongly monotone on an open set is that all the eigenvalues of the symmetric part of its Jacobian be bounded below by a positive constant on the given set.This research constituted a part of the author's Ph.D. dissertation at the University of California at Berkeley, Berkeley, California. The author would like to express his appreciation to Professor G. B. Dantzig, who brought this problem to his attention and guided his research with his several suggestions and helpful criticism. Also, he thanks the referee for several important comments and recommendations.     

Global optimal solutions to a class of quadrinomial minimization problems with one quadratic constraint

This paper studies the canonical duality theory for solving a class of quadrinomial minimization problems subject to one general quadratic constraint. It is shown that the nonconvex primal problem in \mathbb Rⁿ{\mathbb {R}^n} can be converted into a concave maximization dual problem over a convex set in \mathbb R²{\mathbb {R}^2}, such that the problem can be solved more efficiently. The existence and uniqueness theorems of global minimizers are provided using the triality theory. Examples are given to illustrate the results obtained.     

X-rays of polygons

Various results are given concerning X-rays of polygons in ². It is shown that no finite set of X-rays determines every star-shaped polygon, partially answering a question of S. Skiena. For anyn, there are simple polygons which cannot be verified by any set ofn X-rays. Convex polygons are uniquely determined by X-rays at any two points. Finally, it is proved that given a convex polygon, certain sets of three X-rays will distinguish it from other Lebesgue measurable sets.This work was done at the Istituto Analisi Globale e Applicazioni, Florence, Italy.     

Convex mean curvature flow with a forcing term in direction of the position vector

A smooth, compact and strictly convex hypersurface evolving in ℝ ⁿ⁺¹ along its mean curvature vector plus a forcing term in the direction of its position vector is studied in this paper. We show that the convexity is preserving as the case of mean curvature flow, and the evolving convex hypersurfaces may shrink to a point in finite time if the forcing term is small, or exist for all time and expand to infinity if it is large enough. The flow can converge to a round sphere if the forcing term satisfies suitable conditions which will be given in the paper. Long-time existence and convergence of normalization of the flow are also investigated.     

Finding the convex hull of a simple polygon

It is well known that the convex hull of a set of n points in the plane can be found by an algorithm having worst-case complexity O(n log n). A short linear-time algorithm for finding the convex hull when the points form the (ordered) vertices of a simple (i.e., non-self-intersecting) polygon is given.     

The space clcv(? n ) with the Hausdorff-Bebutov metric and statistically invariant sets of control systems

We obtain conditions that allow one to evaluate the relative frequency of occurrence of the reachable set of a control system in a given set. If the relative frequency of occurrence in this set is 1, then the set is said to be statistically invariant. It is assumed that the images of the right-hand side of the differential inclusion corresponding to the given control system are convex, closed, but not necessarily compact. We also study the basic properties of the space clcv(? ⁿ ) of nonempty closed convex subsets of ? ⁿ with the Hausdorff-Bebutov metric.     

On transfer inequalities in Diophantine approximation, II

Let Θ be a point in R ⁿ . We are concerned with the approximation to Θ by rational linear subvarieties of dimension d for 0 ≤ d ≤ n−1. To that purpose, we introduce various convex bodies in the Grassmann algebra Λ(R ⁿ⁺¹). It turns out that our convex bodies in degree d are the dth compound, in the sense of Mahler, of convex bodies in degree one. A dual formulation is also given. This approach enables us both to split and to refine the classical Khintchine transference principle.     

Slice-Continuous Sets in Reflexive Banach Spaces: Some Complements

In this paper we study a class of closed convex sets introduced recently by Ernst et al. (J Funct Anal 223:179–203, 2005) and called by these authors slice-continuous sets. This class, which plays an important role in the strong separation of convex sets, coincides in ℝ ⁿ with the well known class of continuous sets defined by Gale and Klee in the 1960s. In this article we achieve, in the setting of reflexive Banach spaces, two new characterizations of slice-continuous sets, similar to those provided for continuous sets in ℝ ⁿ by Gale and Klee. Thus, we prove that a slice-continuous set is precisely a closed and convex set which does not possess neither boundary rays, nor flat asymptotes of any dimension. Moreover, a slice-continuous set may also be characterized as being a closed and convex set of non-void interior for which the support function is continuous except at the origin. Dedicated to Boris Mordukhovich in honour of his 60th birthday.     

Evaluating inclusion functionals for random convex hulls

Summary The inclusion functional of a random convex set, evaluated at a fixed convex set K, measures the probability that the random convex set contains K. This functional is an analogue of the complement of the distribution function of an ordinary random variable. A methodology is described for evaluating the inclusion functional for the case where the random convex set is generated as the convex hull of n i.i.d. points from a distribution function F in the plane. For general K and F, the inclusion probability is difficult to compute in closed form. The case where K is a straight line segment is examined in detail and, in this situation, a simple answer is given for an interesting class of distributions F.     

How to compute the volume in high dimension?

 In some areas of theoretical computer science we feel that randomized algorithms are better and in some others we can prove that they are more efficient than the deterministic ones. Approximating the volume of a convex n-dimensional body, given by an oracle is one of the areas where this difference can be proved. In general, if we use a deterministic algorithm to approximate the volume, it requires exponentially many oracle questions in terms of n as n→∞. Dyer, Frieze and Kannan gave a randomized polynomial approximation algorithm for the volume of a convex body K⊆ℝ ⁿ , given by a membership oracle. The DKF algorithm was improved in a sequence of papers. The area is full of deep and interesting problems and results. This paper is an introduction to this field and also a survey. Received: January 28, 2003 / Accepted: April 29, 2003 Published online: May 28, 2003     

Computing Mixed Discriminants, Mixed Volumes, and Permanents

We construct a probabilistic polynomial time algorithm that computes the mixed discriminant of given n positive definite matrices within a 2 ^O(n) factor. As a corollary, we show that the permanent of an nonnegative matrix and the mixed volume of n ellipsoids in R ⁿ can be computed within a 2 ^O(n) factor by probabilistic polynomial time algorithms. Since every convex body can be approximated by an ellipsoid, the last algorithm can be used for approximating in polynomial time the mixed volume of n convex bodies in R ⁿ within a factor n ^O(n) . Received July 10, 1995, and in revised form May 20, 1996.