Finding the nearest point in A polytope

A terminating algorithm is developed for the problem of finding the point of smallest Euclidean norm in the convex hull of a given finite point set in Euclideann-space, or equivalently for finding an optimal hyperplane separating a given point from a given finite point set. Its efficiency and accuracy are investigated, and its extension to the separation of two sets and other convex programming problems described.     

Delaunay triangulation and the convex hull ofn points in expected linear time

An algorithm is presented which produces a Delaunay triangulation ofn points in the Euclidean plane in expected linear time. The expected execution time is achieved when the data are (not too far from) uniformly distributed. A modification of the algorithm discussed in the appendix treats most of the non-uniform distributions. The basis of this algorithm is a geographical partitioning of the plane into boxes by the well-known Radix-sort algorithm. This partitioning is also used as a basis for a linear time algorithm for finding the convex hull ofn points in the Euclidean plane.     

An algorithm for finding the Chebyshev center of a convex polyhedron

An algorithm for finding the Chebyshev center of a finite point set in the Euclidean spaceR ⁿ is proposed. The algorithm terminates after a finite number of iterations. In each iteration of the algorithm the current point is projected orthogonally onto the convex hull of a subset of the given point set.Part of this research was done at the University of Würzburg (Institut für Angewandte Mathematik und Statistik) when the first author was supported by the Alexander von Humboldt Foundation, Germany.On leave from the Institute of Mathematics and Mechanics, Ural Department of Russia Academy of Sciences, 620219 Ekaterinburg, S. Kovalevskaya str.16, Russia.     

The two-convex-polygons TSP: A solvable case

In this paper, the Travelling Salesman Problem whenm points are on one convex polygonP, andn points are on another convex polygonQ, insideP, is polynomially solved. For this specific case, anO(m ³ n ³) time andO(m ² n ²) space algorithm to obtain the tour with minimum length is provided.     

Paths in graphs,reducing the edge-connectivity only by two

For every pair of verticesx andy in a connected, finite, undirected graphG, there is a pathP joiningx andy such that deleting the edges ofP fromG, for every pair of vertices ofG, the local edge-connectivity decreases by at most two.     

Randomized algorithms for the separation of point sets and for solving quadratic programs

A randomized algorithm for finding a hyperplane separating two finite point sets in the Euclidean space ^d and a randomized algorithm for solving linearly constrained general convex quadratic problems are proposed. The expected running time of the separating algorithm isO(dd! (m + n)), wherem andn are cardinalities of sets to be separated. The expected running time of the algorithm for solving quadratic problems isO(dd! s) wheres is the number of inequality constraints. These algorithms are based on the ideas of Seidel's linear programming algorithm [6]. They are closely related to algorithms of [8], [2], and [9] and belong to an abstract class of algorithms investigated in [1]. The algorithm for solving quadratic problems has some features of the one proposed in [7].This research was done when the author was supported by the Alexander von Humboldt Foundation, Germany.On leave from the Institute of Mathematics and Mechanics, Ural Department of the Russian Academy of Sciences, 620219 Ekaterinburg, S. Kovalevskaya str. 16, Russia.     

Numerical decomposition of a convex function

Given then×p orthogonal matrixA and the convex functionf:R ⁿR, we find two orthogonal matricesP andQ such thatf is almost constant on the convex hull of ± the columns ofP, f is sufficiently nonconstant on the column space ofQ, and the column spaces ofP andQ provide an orthogonal direct sum decomposition of the column space ofA. This provides a numerically stable algorithm for calculating the cone of directions of constancy, at a pointx, of a convex function. Applications to convex programming are discussed.This work was supported by the National Science and Engineering Research Council of Canada (Grant No. A3388 and Summer Grant).     

Note on a method of conjugate subgradients for minimizing nondifferentiable functions

An algorithm is described for finding the minimum of any convex, not necessarily differentiable, functionf of several variables. The algorithm yields a sequence of points tending to the solution of the problem, if any; it requires the calculation off and one subgradient off at designated points. Its rate of convergence is estimated for convex and also for twice differentiable convex functions. It is an extension of the method of conjugate gradients, and terminates whenf is quadratic. Editor's note. The communications of Wolfe and Lemarechal which follow — received almost simultaneously — display different points of view, but deal with the same problem and use similar techniques. They are preliminary versions of promising attacks on the problem of minimizing a convex, but not necessarily differentiable, function of many variables. MATHEMATICAL PROGRAMMING STUDY 3 entitledNondifferentiable optimization is to be devoted to this subject.     

Sets in a euclidean space which are not a countable union of convex subsets

We prove that if a closed planar setS is not a countable union of convex subsets, then exactly one of the following holds:

Subdivision of simplices relative to a cutting plane and finite concave minimization

In this article, our primary concern is the classical problem of minimizing globally a concave function over a compact polyhedron (Problem (P)). We present a new simplicial branch and bound approach, which combines triangulations of intersections of simplices with halfspaces and ideas from outer approximation in such a way, that a class of finite algorithms for solving (P) results. For arbitrary compact convex feasible sets one obtains a not necessarily finite but convergent algorithm. Theoretical investigations include determination of the number of simplices in each applied triangulation step and bounds on the number of iterations in the resulting algorithms. Preliminary numerical results are given, and additional applications are sketched.     

Algorithmic equivalence in quadratic programming,I: A least-distance programming problem

It is demonstrated that Wolfe's algorithm for finding the point of smallest Euclidean norm in a given convex polytope generates the same sequence of feasible points as does the van de Panne-Whinstonsymmetric algorithm applied to the associated quadratic programming problem. Furthermore, it is shown how the latter algorithm may be simplified for application to problems of this type.This work was supported by the National Science Foundation, Grant No. MCS-71-03341-AO4, and by the Office of Naval Research, Contract No. N00014-75-C-0267.     

An acyclicity theorem for cell complexes ind dimension

LetC be a cell complex ind-dimensional Euclidean space whose faces are obtained by orthogonal projection of the faces of a convex polytope ind+ 1 dimensions. For example, the Delaunay triangulation of a finite point set is such a cell complex. This paper shows that the in_front/behind relation defined for the faces ofC with respect to any fixed viewpointx is acyclic. This result has applications to hidden line/surface removal and other problems in computational geometry.Research reported in this paper was supported by the National Science Foundation under grant CCR-8714565     

An interior points algorithm for the convex feasibility problem

The problem of finding a point in the intersection of a finite family of convex sets in the Euclidean space R″ is considered here. We present a general algorithmic scheme which employs projections onto separating hyperplanes instead of projections onto the convex sets. This scheme includes the method of successive projections of Gubin et al., USSR Comp. Math. and Math. Phys. 7 (1967), 1–24, as a special case. A different realization proposed here is capable of handling the problem when the sets are solid and an interior point of each set is available. This alternative algorithm may, in certain cases, be more attractive than the method of Gubin et al.     

On bending of a convex surface to a convex surface with prescribed spherical image

We prove the following theorem. LetF be a regular convex surface homeomorphic to the disk. Suppose the Gaussian curvature ofF is positive and the geodesic curvature of its boundary is positive as well. LetG be a convex domain on the unit sphere bounded by a smooth curve and strictly contained in a hemisphere. LetP be an arbitrary point on the boundary ofF andP ^* be an arbitrary point on the boundary ofG. If the area ofG is equal to the integral curvature of the surfaceF, then there exists a continuous bending of the surfaceF to a convex surfaceF such that the spherical image ofF coincides withG andP ^* is the image of the point inF corresponding to the pointP F under the isometry.Translated fromMatematicheskie Zametki, Vol. 58, No. 2, pp. 295–300, August, 1995.     

AnO(n logn) algorithm for computing the link center of a simple polygon

We present an algorithm that determines the link center of a simplen-vertex polygonP inO(n logn) time. The link center of a simple polygon is the set of pointsx insideP at which the maximal link-distance fromx to any other point inP is minimized. The link distance between two pointsx andy insideP is defined to be the smallest number of straight edges in a polygonal path insideP connectingx andy. Using our algorithm we also obtain anO(n logn)-time solution to the problem of determining the link radius ofP. The link radius ofP is the maximum link distance from a point in the link center to any vertex ofP. Both results are improvements over theO(n ²) bounds previously established for these problems. The research of J.-R. Sack was supported by the Natural Sciences and Engineering Research Council of Canada.     

Safety Zone Problem

Given a simple polygon P, its safety zone S (of width δ) is a closed region consisting of straight line segments and circular arcs (of radius δ) bounding the polygon P such that there exists no pair of points p (on the boundary of P) and q (on the boundary of S) having their Euclidean distance d(p, q) less than δ. In this paper we present a linear time algorithm for finding the minimum area safety zone of an arbitrarily shaped simple polygon. It is also shown that our proposed method can easily be modified to compute the Minkowski sum of a simple polygon and a convex polygon in O(MN) time, where M and N are the number of vertices of both the polygons.     

On sets having finitely many points of local nonconvexity and propertyP m

If a pointq ofS has the property that each neighborhood ofq contains pointsx andy such that the segmentxy is not contained byS, q is called a point of local nonconvexity ofS. LetQ denote the set of points of local nonconvexity ofS. Tietze’s well known theorem that a closed connected setS in a linear topological space is convex ifQ=φ is generalized in the result:If S is a closed set in a linear topological space such that S ∼ Q is connected and |Q|=n<∞,then S is the union of n+1or fewer closed convex sets. Letk be the minimal number of convex sets needed in a convex covering ofS. Bounds fork in terms ofm andn are obtained for sets having propertyP _m and |Q|=n.     

Right angle free subsets in the plane

In this paper we investigate the complexity of finding maximum right angle free subsets of a given set of points in the plane. For a set of rational pointsP in the plane, theright angle number (P) (respectivelyrectilinear right angle number _R (P)) ofP is the cardinality of a maximum subset ofP, no three members of which form a right angle triangle (respectively a right angle triangle with its side or base parallel to thex-axis). It is shown that both parameters areNP-hard to compute. The latter problem is also shown to be equivalent to finding a minimum dominating set in a bipartite graph. This is used to show that there is a polynomial algorithm for computing _R (P) whenP is a horizontally-convex subset of the lattice × (P ishorizontally-convex if for any pair of points inP which lie on a horizontal line, every lattice point between them is also inP). We then show that this algorithm yields a 1/2-approximate algorithm for the right angle number of a convex subregion of the lattice.     

A Dual Approach to Constrained Interpolationfrom a Convex Subset of Hilbert Space

Many interesting and important problems of best approximationare included in (or can be reduced to) one of the followingtype: in a Hilbert spaceX, find the best approximationP_K(x) to anyxXfrom the setKC∩A⁻¹(b),whereCis a closed convex subset ofX,Ais a bounded linearoperator fromXinto a finite-dimensional Hilbert spaceY, andbY. The main point of this paper is to show thatP_K(x)isidenticaltoP_C(x+A*y)—the best approximationto a certain perturbationx+A*yofx—from the convexsetCor from a certain convex extremal subsetC_bofC. Thelatter best approximation is generally much easier to computethan the former. Prior to this, the result had been known onlyin the case of a convex cone or forspecialdata sets associatedwith a closed convex set. In fact, we give anintrinsic characterizationof those pairs of setsCandA⁻¹(b) for which this canalways be done. Finally, in many cases, the best approximationP_C(x+A*y) can be obtained numerically from existingalgorithms or from modifications to existing algorithms. Wegive such an algorithm and prove its convergence     

Convex Minimization on a Grid and Applications

This article discusses a discrete version of the convex minimization problem with applications to the efficient computation of proximity measures for pairs of convex polyhedra. Given ad-variate convex function and an isothetic grid of sizeO(n^d) in ^d, which is supposed to be finite but not necessarily regular, we want to find the grid cell containing the minimum point. With this aim, we identify a class of elementary subproblems, each resulting in the determination of a half-space in ^d, and show that the minimization problem can be solved by computingO(log n) half-spaces in the worst case foralmost uniformgrids of fixed dimensiondandO(log n) half-planes in the average for arbitrary planar grids. A major point is the potential of the approach to uniformly solve distance related problems for different configurations of a pair of convex bodies. In this respect, the case of a bivariate function is of particular interest and leads to a fast algorithm for detecting collisions between two convex polyhedra in three dimensions. The collision algorithm runs inO(log² n) average time for polyhedra withO(n) vertices whose boundaries are suitably represented; more specifically, the 1-skeletons can be embedded into layered Directed Acyclic Graphs which require justO(n) storage. The article ends with a brief discussion of a few experimental results.