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.     

Approximating largest convex hulls for imprecise points

Assume that a set of imprecise points in the plane is given, where each point is specified by a region in which the point will lie. Such a region can be modelled as a circle, square, line segment, etc. We study the problem of maximising the area of the convex hull of such a set. We prove NP-hardness when the imprecise points are modelled as line segments, and give linear time approximation schemes for a variety of models, based on the core-set paradigm.     

Evaluation of nondominated solution sets for k-objective optimization problems: An exact method and approximations

Integrated Preference Functional (IPF) is a set functional that, given a discrete set of points for a multiple objective optimization problem, assigns a numerical value to that point set. This value provides a quantitative measure for comparing different sets of points generated by solution procedures for difficult multiple objective optimization problems. We introduced the IPF for bi-criteria optimization problems in [Carlyle, W.M., Fowler, J.W., Gel, E., Kim, B., 2003. Quantitative comparison of approximate solution sets for bi-criteria optimization problems. Decision Sciences 34 (1), 63–82]. As indicated in that paper, the computational effort to obtain IPF is negligible for bi-criteria problems. For three or more objective function cases, however, the exact calculation of IPF is computationally demanding, since this requires k (⩾3) dimensional integration.In this paper, we suggest a theoretical framework for obtaining IPF for k (⩾3) objectives. The exact method includes solving two main sub-problems: (1) finding the optimality region of weights for all potentially optimal points, and (2) computing volumes of k dimensional convex polytopes. Several different algorithms for both sub-problems can be found in the literature. We use existing methods from computational geometry (i.e., triangulation and convex hull algorithms) to develop a reasonable exact method for obtaining IPF. We have also experimented with a Monte Carlo approximation method and compared the results to those with the exact IPF method.     

A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes

For a given pair of finite point setsP andQ in some Euclidean space we consider two problems: Problem 1 of finding the minimum Euclidean norm point in the convex hull ofP and Problem 2 of finding a minimum Euclidean distance pair of points in the convex hulls ofP andQ. We propose a finite recursive algorithm for these problems. The algorithm is not based on the simplicial decomposition of convex sets and does not require to solve systems of linear equations.     

Closed convex hulls,contents, and K‐spectral states

Our general result says that the closed convex hull of a set K consists of barycentres of probability contents (i.e., finitely additive set functions) on K. (Here K can be any nonempty subset of any nonempty compact convex set in any real or complex locally convex Hausdorff vector space.) In the equivalent setting of dual spaces, we give a very handy analytic criterion for a linear functional to be in the closed convex hull of a given nonempty point‐wise bounded set K of linear functionals (under some mild additional assumption). This is the notion of a K‐spectral state. Our criterion enhances the Abstract Bochner Theorem for unital commutative Banach *‐algebras (which easily follows from our result), in that it allows us to prescribe the set K on which a representing content should live. The content can be chosen to be a Radon measure if K is weak* compact. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Dynamization of order decomposable set problems

Order decomposable set problems are introduced as a general class of problems concerning sets of multidimensional objects. We give a method of structuring sets such that the answer to an order decomposable set problem can be maintained with low worst-case time bounds, while objects are inserted and deleted in the set. Examples include the maintenance of the two-dimensional Voronoi diagram of a set of points, and of the convex hull of a three-dimensional point set in linear time. We show that there is a strong connection between the general dynamization method given and the well-known technique of divide-and-conquer used for solving many problems concerning static sets of objects. Although the upper bounds obtained are low in order of magnitude, the results do not necessarily imply the existence of fast feasible update routines. Hence the results merely assess theoretical bounds for the various set problems considered.     

Polyhedral approximation and practical convex hull algorithm for certain classes of voxel sets

In this paper we introduce an algorithm for the creation of polyhedral approximations for certain kinds of digital objects in a three-dimensional space. The objects are sets of voxels represented as strongly connected subsets of an abstract cell complex. The proposed algorithm generates the convex hull of a given object and modifies the hull afterwards by recursive repetitions of generating convex hulls of subsets of the given voxel set or subsets of the background voxels. The result of this method is a polyhedron which separates object voxels from background voxels. The objects processed by this algorithm and also the background voxel components inside the convex hull of the objects are restricted to have genus 0. The second aim of this paper is to present some practical improvements to the discussed convex hull algorithm to reduce computation time.     

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.     

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.     

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.     

One approach to constructing a minimal convex hull

The minimal convex hull of a subset of finite-dimensional space is constructed in a discrete fashion: at each step, we construct a new set that includes the inherited set. The procedure for finding the chain of sets involves geometrically evident constructions. This chain becomes stationary; i.e., from some number onward, all the sets of the chain being constructed coincide with the minimal convex hull. Our approach uses the principal result (Caratheodory’s theorem) underlying the conventional approach to constructing a minimal convex hull.     

Approximating a real number by a rational number with a limited denominator: A geometric approach

We consider the problem of determining the rational number which best approximates the real number a and such that its denominator belongs to an interval [b,b^′]. There is a related geometric problem consisting in finding the integer point lying in the vertical domain D of the form {(x,y)∈R²∣b≤x≤b^′} such that the straight line passing through the origin and through this point best approximates the straight line L of slope a passing through the origin. The computation of this point is interlinked with the computation of both the convex hulls of the integer points located above and below the straight line L respectively and lying in the vertical domain D. In the literature, many general convex hull algorithms exist, as the gift wrapping algorithm for example. However, we focus on two interesting approaches to compute these convex hulls which are especially appropriated in our special configuration. The first one mainly uses number theory and runs in O(log(b^′)) time. The other is in line with computational geometry as the method proposed in 1999 by Balza-Gomez et al. [H. Balza-Gomez, J.-M. Moreau, D. Michelucci, Convex hull of grid points below a line or a convex curve, in: DGCI ’99: Proceedings of the 8th International Conference on Discrete Geometry for Computer Imagery, Springer, Marne-la-Vallée, France, 1999, pp. 361-374] which runs in O(log(b^′−b)) time. We propose a new method for the computation of these convex hulls which combines number theory and computational geometry. Our method preserves the optimal time complexity and is the first being output sensitive. Indeed, we compute the convex hulls in time linear in their vertex number. Moreover, the resulting algorithm is very simple and so is suitable for implementation.     

Analyzing linear systems containing strict inequalities via evenly convex hulls

The evenly convex hull of a given set is the intersection of all the open halfspaces which contain such set (hence the convex hull is contained in the evenly convex hull). This paper deals with finite dimensional linear systems containing strict inequalities and (possibly) weak inequalities as well as equalities. The number of inequalities and equalities in these systems is arbitrary (possibly infinite). For such kind of systems a consistency theorem is provided and those strict inequalities (weak inequalities, equalities) which are satisfied for every solution of a given system are characterized. Such results are formulated in terms of the evenly convex hull of certain sets which depend on the coefficients of the system.     

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.     

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.     

Non-crossing matchings of points with geometric objects

Given an ordered set of points and an ordered set of geometric objects in the plane, we are interested in finding a non-crossing matching between point–object pairs. In this paper, we address the algorithmic problem of determining whether a non-crossing matching exists between a given point–object pair. We show that when the objects we match the points to are finite point sets, the problem is NP-complete in general, and polynomial when the objects are on a line or when their size is at most 2. When the objects are line segments, we show that the problem is NP-complete in general, and polynomial when the segments form a convex polygon or are all on a line. Finally, for objects that are straight lines, we show that the problem of finding a min-max non-crossing matching is NP-complete.     

A simple algorithm for building the 3-D convex hull

A new algorithm is given for finding the convex hull of a finite set of distinct points in three-dimensional space. The algorithm finds the faces of the hull one by one, thus gradually building the polyhedron that constitutes the hull. The algorithm is described as developed through stepwise refinement.     

Minimum Distance to the Complement of a Convex Set: Duality Result

The subject of this paper is to study the problem of the minimum distance to the complement of a convex set. Nirenberg has stated a duality theorem treating the minimum norm problem for a convex set. We state a duality result which presents some analogy with the Nirenberg theorem, and we apply this result to polyhedral convex sets. First, we assume that the polyhedral set is expressed as the intersection of some finite collection of m given half-spaces. We show that a global solution is determined by solving m convex programs. If the polyhedral set is expressed as the convex hull of a given finite set of extreme points, we show that a global minimum for a polyhedral norm is obtained by solving a finite number of linear programs.