An Accurate Distance Algorithm for Octree‐Encoded Objects

Distance algorithms are most frequently used in robotics to determine the distance between two obstacles in the environment of a robot or between a sensor point and an object. Bounding volumes are a common technique; this technique relies on a hierarchical model representation of the two surfaces using axis‐aligned bounding boxes. Formoving objects it is interesting to use unaligned octrees to avoid the wrapping effect that occurs when performing octree decomposition in a common coordinate system after several rotations. We discuss the algorithm for computing accurate enclosures for the distance between objects represented by axis‐aligned or unaligned octrees. This algorithm is based on a new, recently published distance algorithm between two objects represented by axis‐aligned octrees. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Limit theorems for functionals of convex hulls

Summary In [4] a central limit theorem for the number of vertices of the convex hull of a uniform sample from the interior of a convex polygon is derived. This is done by approximating the process of vertices of the convex hull by the process of extreme points of a Poisson point process and by considering the latter process of extreme points as a Markov process (for a particular parametrization). We show that this method can also be applied to derive limit theorems for the boundary length and for the area of the convex hull. This extents results of Rényi and Sulanke (1963) and Buchta (1984), and shows that the boundary length and the area have a strikingly different probabilistic behavior.     

On the Application of Accurate Distance Algorithms to Multibody Simulations

Distance algorithms are most frequently used in robotics to determine the distance between two obstacles in the environment of a robot or between a sensor point and an object. We extend the multibody simulation package MOBILE for an application of accurate algorithms for distance computation between objects represented by convex or non-convex polyhedra. These objects are represented by their vertices and oriented facets. As an application example, a multibody system is discussed where a sensor point moves close to a non-convex obstacle. The computed results show that the algorithms developed are suitable for accurate real-time multibody simulations. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Verified Distance Computation Between Convex Hulls of Octrees Using Interval Optimization Techniques

Distance computation is an important task in many application areas, including biomechanics, robot systems and computer games. Depending on the intended use, requirements differ. For example, in a medical context, a verified result may be of interest. In this paper we will demonstrate the use of an interval optimization algorithm for computing a verified enclosure of the minimum distance between the convex hulls of two octrees. We will also discuss runtime improvements. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Polyhedral studies on the convex recoloring problem

A coloring of the vertices of a graph G is convex if, for each assigned color d, the vertices with color d induce a connected subgraph of G. We address the convex recoloring problem, defined as follows. Given a graph G and a coloring of its vertices, recolor a minimum number of vertices of G, so that the resulting coloring is convex. This problem is known to be NP-hard even when G is a path. We show an integer programming formulation for the weighted version of this problem on arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and discuss separation algorithms.     

Automorphisms and Distinguishing Numbers of Geometric Cliques

A geometric automorphism is an automorphism of a geometric graph that preserves crossings and noncrossings of edges. We prove two theorems constraining the action of a geometric automorphism on the boundary of the convex hull of a geometric clique. First, any geometric automorphism that fixes the boundary of the convex hull fixes the entire clique. Second, if the boundary of the convex hull contains at least four vertices, then it is invariant under every geometric automorphism. We use these results, and the theory of determining sets, to prove that every geometric n-clique in which n≥7 and the boundary of the convex hull contains at least four vertices is 2-distinguishable.     

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.     

Convex hull-based multi-objective evolutionary computation for maximizing receiver operating characteristics performance

The receiver operating characteristics (ROC) analysis has gained increasing popularity for analyzing the performance of classifiers. In particular, maximizing the convex hull of a set of classifiers in the ROC space, namely ROCCH maximization, is becoming an increasingly important problem. In this work, a new convex hull-based evolutionary multi-objective algorithm named ETriCM is proposed for evolving neural networks with respect to ROCCH maximization. Specially, convex hull-based sorting with convex hull of individual minima (CH-CHIM-sorting) and extreme area extraction selection (EAE-selection) are proposed as a novel selection operator. Empirical studies on 7 high-dimensional and imbalanced datasets show that ETriCM outperforms various state-of-the-art algorithms including convex hull-based evolutionary multi-objective algorithm (CH-EMOA) and non-dominated sorting genetic algorithm II (NSGA-II).     

平面有限点集中的最大面积六边形

若平面上的有限点集构成凸多边形的顶点集,则称此有限点集处于凸位置令P表示平面上处于凸位置的有限点集,研究了P的子集所确定的凸六边形的面积与CH(P)面积比值的最大值问题.     

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.     

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.     

Limit theorems for convex hulls

It is shown that the process of vertices of the convex hull of a uniform sample from the interior of a convex polygon converges locally, after rescaling, to a strongly mixing Markov process, as the sample size tends to infinity. The structure of the limiting Markov process is determined explicitly, and from this a central limit theorem for the number of vertices of the convex hull is derived. Similar results are given for uniform samples from the unit disk.     

Computing Hereditary Convex Structures

Color red and blue the n vertices of a convex polytope \(\mathcal{P}\) in ?³. Can we compute the convex hull of each color class in o(nlog?n) time? What if we have more than two colors? What if the colors are random? Consider an arbitrary query halfspace and call the vertices of \(\mathcal{P}\) inside it blue: can the convex hull of the blue points be computed in time linear in their number? More generally, can we quickly compute the blue hull without looking at the whole polytope? This paper considers several instances of hereditary computation and provides new results for them. In particular, we resolve an eight-year old open problem by showing how to split a convex polytope in linear expected time.     

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.     

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.     

Minimum L1-Distance Projection onto the Boundary of a Convex Set: Simple Characterization

We show that the minimum distance projection in the L ₁-norm from an interior point onto the boundary of a convex set is achieved by a single, unidimensional projection. Application of this characterization when the convex set is a polyhedron leads to either an elementary minmax problem or a set of easily solved linear programs, depending upon whether the polyhedron is given as the intersection of a set of half spaces or as the convex hull of a set of extreme points. The outcome is an easier and more straightforward derivation of the special case results given in a recent paper by Briec (Ref. 1).     

Representations of Affine Multifunctions by Affine Selections

The paper deals with affine selections of affine (both convex and concave) multifunctions acting between finite-dimensional real normed spaces. It is proved that each affine multifunction with compact values possesses an exhaustive family of affine selections and, consequently, can be represented by its affine selections. Moreover, a convex multifunction with compact values possesses an exhaustive family of affine selections if and only if it is affine. Thus the existence of an exhaustive family of affine selections is the characteristic feature of affine multifunctions which differs them from other convex multifunctions with compact values. Besides a necessary and sufficient condition for a concave multifunction to be affine on a given convex subset is also proved. Finally it is shown that each affine multifunction with compact values can be represented as the closed convex hull of its exposed affine selections and as the convex hull of its extreme affine selections. These statements extend the Straszewicz theorem and the Krein–Milman theorem to affine multifunctions. Dedicated to Boris Mordukhovich in honour of his 60th birthday.     

The convex hull of antichains in posets

Extending a result of Kleitman et al. [7] it is shown that the vertices on the convex hull off-vectors of all antichains of a poset come from antichains which are the unions of full orbits of the automorphism group.