Regularization methods for optimization problems with probabilistic constraints

We analyze nonlinear stochastic optimization problems with probabilistic constraints on nonlinear inequalities with random right hand sides. We develop two numerical methods with regularization for their numerical solution. The methods are based on first order optimality conditions and successive inner approximations of the feasible set by progressive generation of p-efficient points. The algorithms yield an optimal solution for problems involving α-concave probability distributions. For arbitrary distributions, the algorithms solve the convex hull problem and provide upper and lower bounds for the optimal value and nearly optimal solutions. The methods are compared numerically to two cutting plane methods.     

Using Interval Arithmetic for Determining the Structure of Convex Hulls

We discuss the use of interval arithmetic in the computation of the convex hull of n points in D dimensions. Convex hull algorithms rely on simple geometric tests, such as “does some point p lie in a certain half-space or affine subspace?” to determine the structure of the hull. These tests in turn can be carried out by solving appropriate (not necessarily square) linear systems. If interval-based methods are used for the solution of these systems then the correct hull can be obtained at lower cost than with exact arithmetic. In addition, interval-based methods can determine the topological structure of the convex hull even if the position of the points is not known exactly. In the present paper we compare various interval linear solvers with respect to their ability to handle close-to-pathological situations. This property determines how often interval arithmetic cannot provide the required information and therefore some computations must be redone with exact arithmetic.     

Finding the convex hull facet by facet

Finding the convex hull of a finite set of points in Euclidean space was one of the first problems explored in the field of computational geometry. In two dimensions a variety of algorithms have been developed and analyzed. For higher dimensions the problems are less well understood. Several “convex hull” problems are defined, solved, and analyzed here in terms of the size of the input and output. In all cases these solutions are the best of the known algorthms. The problems include enumerating the facets of the convex hull, computing the facial lattice of the convex hull and producing a new compact structure representing the combinatorial type of the convex hull. In addition, deciding the combinatorial equivalence of two polytopes is shown to be coNP-hard.     

A comparison of sequential Delaunay triangulation algorithms

This paper presents an experimental comparison of a number of different algorithms for computing the Delaunay triangulation. The algorithms examined are: Dwyer's divide and conquer algorithm, Fortune's sweepline algorithm, several versions of the incremental algorithm (including one by Ohya, Iri and Murota, a new bucketing-based algorithm described in this paper, and Devillers's version of a Delaunay-tree based algorithm that appears in LEDA), an algorithm that incrementally adds a correct Delaunay triangle adjacent to a current triangle in a manner similar to gift wrapping algorithms for convex hulls, and Barber's convex hull based algorithm.

Most of the algorithms examined are designed for good performance on uniformly distributed sites. However, we also test implementations of these algorithms on a number of non-uniform distributions. The experiments go beyond measuring total running time, which tends to be machine-dependent. We also analyze the major high-level primitives that algorithms use and do an experimental analysis of how often implementations of these algorithms perform each operation.     

Extreme point and halving edge search in abstract order types

Many properties of finite point sets only depend on the relative position of the points, e.g., on the order type of the set. However, many fundamental algorithms in computational geometry rely on coordinate representations. This includes the straightforward algorithms for finding a halving line for a given planar point set, as well as finding a point on the convex hull, both in linear time. In his monograph Axioms and Hulls, Knuth asks whether these problems can be solved in linear time in a more abstract setting, given only the orientation of each point triple, i.e., the set?s chirotope, as a source of information. We answer this question in the affirmative. More precisely, we can find a halving line through any given point, as well as the vertices of the convex hull edges that are intersected by the supporting line of any two given points of the set in linear time. We first give a proof for sets realizable in the Euclidean plane and then extend the result to non-realizable abstract order types.     

Reprint of: Extreme point and halving edge search in abstract order types

Many properties of finite point sets only depend on the relative position of the points, e.g., on the order type of the set. However, many fundamental algorithms in computational geometry rely on coordinate representations. This includes the straightforward algorithms for finding a halving line for a given planar point set, as well as finding a point on the convex hull, both in linear time. In his monograph Axioms and Hulls, Knuth asks whether these problems can be solved in linear time in a more abstract setting, given only the orientation of each point triple, i.e., the setʼs chirotope, as a source of information. We answer this question in the affirmative. More precisely, we can find a halving line through any given point, as well as the vertices of the convex hull edges that are intersected by the supporting line of any two given points of the set in linear time. We first give a proof for sets realizable in the Euclidean plane and then extend the result to non-realizable abstract order types.     

On the complexity of finding the convex hull of a set of points

An n log n lower bound is found for linear decision tree algorithms with integer inputs that either identify the convex hull of a set of points or compute its cardinality.     

Optimal output-sensitive convex hull algorithms in two and three dimensions

We present simple output-sensitive algorithms that construct the convex hull of a set ofn points in two or three dimensions in worst-case optimalO (n logh) time andO (n) space, whereh denotes the number of vertices of the convex hull. This research was supported by a Killam Predoctoral Fellowship and an NSERC Postgraduate Scholarship.     

Optimal convex hull algorithms on enhanced meshes

In this paper we propose time-optimal convex hull algorithms for two classes of enhanced meshes. Our first algorithm computes the convex hull of an arbitrary set ofn points in the plane inO (logn) time on a mesh with multiple broadcasting of sizen×n. The second algorithm shows that the same problem can be solved inO (1) time on a reconfigurable mesh of sizen×n. Both algorithms achieve time lower bounds for their respective model of computation.This work was supported by NASA under grant NCCI-99.Additional support by the National Science Foundation under grant CCR-8909996 is gratefully acknowledged.     

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.     

A new systolic architecture for convex hull and half-plane intersection problems

In this paper we will present systolic algorithms for static versions of the convex hull problem and the half-plane intersection problem. The systolic algorithms are based on a cyclic shift operation that makes each object meet all the other objects.     

Applications of random sampling in computational geometry,II

We use random sampling for several new geometric algorithms. The algorithms are Las Vegas, and their expected bounds are with respect to the random behavior of the algorithms. These algorithms follow from new general results giving sharp bounds for the use of random subsets in geometric algorithms. These bounds show that random subsets can be used optimally for divide-and-conquer, and also give bounds for a simple, general technique for building geometric structures incrementally. One new algorithm reports all the intersecting pairs of a set of line segments in the plane, and requiresO(A+n logn) expected time, whereA is the number of intersecting pairs reported. The algorithm requiresO(n) space in the worst case. Another algorithm computes the convex hull ofn points inE ^d inO(n logn) expected time ford=3, andO(n ^[d/2]) expected time ford>3. The algorithm also gives fast expected times for random input points. Another algorithm computes the diameter of a set ofn points inE ³ inO(n logn) expected time, and on the way computes the intersection ofn unit balls inE ³. We show thatO(n logA) expected time suffices to compute the convex hull ofn points inE ³, whereA is the number of input points on the surface of the hull. Algorithms for halfspace range reporting are also given. In addition, we give asymptotically tight bounds for (k)-sets, which are certain halfspace partitions of point sets, and give a simple proof of Lee's bounds for high-order Voronoi diagrams.     

Generating Random Points (or Vectors) Controlling the Percentage of them that Are Extreme in their Convex (or Positive) Hull

This paper presents a technique to generate random data in dimensional space m such that their convex (or positive) hull contains a specific percentage of extreme points (or vectors), determined by the analyst or generator of the data. The methodology strives to remove symmetry, regularity, or predictability, which may be desirable in data used to test or compare algorithms or heuristics. There are numerous applications for this methodology.Mathematics Subject Classifications (2000) 65C10, 52B11, 52B55.     

Verified convex hull and distance computation for octree-encoded objects

This paper discusses algorithms for computing verified convex hull and distance enclosure for objects represented by axis-aligned or unaligned octrees. To find a convex enclosure of an octree, the concept of extreme vertices of boxes on its boundary has been used. The convex hull of all extreme vertices yields an enclosure of the object. Thus, distance algorithms for convex polyhedra to obtain lower bounds for the distance between two octrees can be applied. Since using convex hulls makes it possible to avoid the unwanted wrapping effect that results from repeated decompositions, it also opens a way to dynamic distance algorithms for moving objects.     

Asymptotics of the convex hull of spherically symmetric samples

In this paper we consider the convex hull of a spherically symmetric sample in R^d. Our main contributions are some new asymptotic results for the expectation of the number of vertices, number of facets, area and the volume of the convex hull assuming that the marginal distributions are in the Gumbel max-domain of attraction. Further, we briefly discuss two other models assuming that the marginal distributions are regularly varying or O-regularly varying.     

How to Exhibit Toroidal Maps in Space

Steinitz's theorem states that a graph is the 1-skeleton of a convex polyhedron if and only if it is 3-connected and planar. The polyhedron is called a geometric realization of the embedded graph. Its faces are bounded by convex polygons whose points are coplanar. A map on the torus does not necessarily have such a geometric realization. In this paper we relax the condition that faces are the convex hull of coplanar points. We require instead that the convex hull of the points on a face can be projected onto a plane so that the boundary of the convex hull of the projected points is the image of the boundary of the face. We also require that the interiors of the convex hulls of different faces do not intersect. Call this an exhibition of the map. A map is polyhedral if the intersection of any two closed faces is simply connected. Our main result is that every polyhedral toroidal map can be exhibited. As a corollary, every toroidal triangulation has a geometric realization.     

Algorithmic Complexity of a Problem of Idempotent Convex Geometry

Properties of the idempotently convex hull of a two-point set in a free semimodule over the idempotent semiring R _{max min} and in a free semimodule over a linearly ordered idempotent semifield are studied. Construction algorithms for this hull are proposed.     

Some properties of convex hulls of integer points contained in general convex sets

In this paper, we study properties of general closed convex sets that determine the closedness and polyhedrality of the convex hull of integer points contained in it. We first present necessary and sufficient conditions for the convex hull of integer points contained in a general convex set to be closed. This leads to useful results for special classes of convex sets such as pointed cones, strictly convex sets, and sets containing integer points in their interior. We then present a sufficient condition for the convex hull of integer points in general convex sets to be a polyhedron. This result generalizes the well-known result due to Meyer (Math Program 7:223–225, 1974). Under a simple technical assumption, we show that these sufficient conditions are also necessary for the convex hull of integer points contained in general convex sets to be a polyhedron.     

A shape-preserving approximation by weighted cubic splines

This paper addresses new algorithms for constructing weighted cubic splines that are very effective in interpolation and approximation of sharply changing data. Such spline interpolations are a useful and efficient tool in computer-aided design when control of tension on intervals connecting interpolation points is needed. The error bounds for interpolating weighted splines are obtained. A method for automatic selection of the weights is presented that permits preservation of the monotonicity and convexity of the data. The weighted B-spline basis is also well suited for generation of freeform curves, in the same way as the usual B-splines. By using recurrence relations we derive weighted B-splines and give a three-point local approximation formula that is exact for first-degree polynomials. The resulting curves satisfy the convex hull property, they are piecewise cubics, and the curves can be locally controlled with interval tension in a computationally efficient manner.