Neural networks for convex hull computation

Computing convex hull is one of the central problems in various applications of computational geometry. In this paper, a convex hull computing neural network (CHCNN) is developed to solve the related problems in the N-dimensional spaces. The algorithm is based on a two-layered neural network, topologically similar to ART, with a newly developed adaptive training strategy called excited learning. The CHCNN provides a parallel online and real-time processing of data which, after training, yields two closely related approximations, one from within and one from outside, of the desired convex hull. It is shown that accuracy of the approximate convex hulls obtained is around O[K^-1(N-1/)], where K is the number of neurons in the output layer of the CHCNN. When K is taken to be sufficiently large, the CHCNN can generate any accurate approximate convex hull. We also show that an upper bound exists such that the CHCNN will yield the precise convex hull when K is larger than or equal to this bound. A series of simulations and applications is provided to demonstrate the feasibility, effectiveness, and high efficiency of the proposed algorithm     

Efficient convex hull computation for planar freeform curves

We present an efficient real-time algorithm for computing the precise convex hulls of planar freeform curves. For this purpose, the planar curves are initially approximated with G¹-biarcs within a given error bound ε in a preprocessing step. The algorithm is based on an efficient construction of approximate convex hulls using circular arcs. The majority of redundant curve segments can be eliminated using simple geometric tests on circular arcs. In several experimental results, we demonstrate the effectiveness of the proposed approach, which shows the performance improvement in the range of 200-300 times speed up compared with the previous results (Elber et al., 2001) [8].     

Time- and storage-efficient implementation of an optimal planar convex hull algorithm

An implementation of an algorithm for computing the convex hull of a finite planar set of points is presented. The program is compared with an algorithm for the same purpose coded previously. Experimental results indicate that our program is superior to the other in terms of both running time and storage requirements.     

Efficient planar convex hull algorithm

A new algorithm for computing the convex hull of a planar set of points is presented. The method of determining the set of suitable candidates is compared with previous algorithms. The algorithm is also compared with other algorithms in terms of running time and storage requirements, and experiments indicate that it is at least as good in terms of space and generally better in terms of running time.     

A convex hull inclusion test

A new characterization of the interior of the convex hull of a finite point set is given. An inclusion test based on this characterization is, on average, almost linear in the number of points times the dimensionality.     

A fast convex hull algorithm

Convex hull, algorithm     

Eigenmodes computation on quadrilateral meshes

We approximate a fluid-structure interaction eigenvalue problem by means of finite elements on quadrilateral meshes. The problem under consideration looks simple and has been the object of a wide investigation: actually, no standard numerical scheme achieves acceptable results in presence of field singularities. We consider a three-field mixed method introduced by Bathe et al. and based on rectangular meshes (see [3, 12]). Recent results show that particular care has to be taken into account when dealing with finite element approximation on general quadrilateral meshes. We present numerical experiments on several sequences of meshes which definitely show how the “local” approach has to be discarded, while the “global” approach gives reasonable results. Received: 30 January 2001 / Accepted: 30 May 2001     

一种鲁棒的可视外壳生成算法*

针对各种传统可视外壳生成算法中数据冗余、精确度低、健壮性不足等问题, 提出了一种新的可视外壳生成算法,即采用加权线段求交、线段集合中心线性过滤、多边形边界检测等方法重建物体模型。与传统方法相比,本算法能够更稳定地计算线段交集,表面边界提取更加准确,重建结果精确逼近真实物体。实验表明, 通过该算法计算的物体可视外壳能够更好地逼近真实模型,精度高。     

A convex hull algorithm for planar simple polygons

A linear convex hull algorithm which is an improvement on the algorithm due to Sklansky is given.     

平面点集凸壳的快速算法

提出一种计算平面点集凸壳的快速算法。利用极值点划分出四个矩形,它们包含了所有凸壳顶点,通过对矩形中的点进行扫描,排除明显不是凸壳顶点的点,剩余的点构成一个简单多边形。再利用极点顺序法判断多边形顶点的凹凸性并删除所出现的凹顶点,最终得到一个凸多边形即为点集的凸壳。整个算法简洁明了,避免了乘法运算（除最坏情况外）,从而节省计算时间。     

PAV and the ROC convex hull

Classifier calibration is the process of converting classifier scores into reliable probability estimates. Recently, a calibration technique based on isotonic regression has gained attention within machine learning as a flexible and effective way to calibrate classifiers. We show that, surprisingly, isotonic regression based calibration using the Pool Adjacent Violators algorithm is equivalent to the ROC convex hull method. Editor: Johannes Fürnkranz.     

Detecting textured objects using convex hull

In this paper, we present a methodology of locating 3D objects of known shapes from a single gray-scale image, in particular objects with rich textures on the surface. While traditional approaches identify objects by grouping and matching local features, we locate the object in the image using its convex hull, a high level feature not given much attention in the image using literature. A “direct line detection” algorithm is developed to detect line segments directly from the gray-scale image divided in small blocks. Lines are clustered and convex hull of a single or group of clusters is computed and edited to extract the 2D contour of the object. Successful experiments on rectangular boxes and cylinders show the effectiveness of the convex hull approach and its potential usage in industrial applications. Part of the work discussed in this paper was performed when both authors were affiliated with Symbol Technologies.     

求两个相交凸多边形并的凸包及交的算法

凸多边形交、并求解的难点在于如何维护结果多边形的顶点序列。利用坐标的极值将凸多边形分成几个段,利用凸壳顶点有序性,分段计算凸壳顶点而得到凸壳。两个相交的凸多边形P和Q,求P和Q并的凸壳通过计算它的4个单调段来进行。每个单调段的点是否是凸壳上的点只与2个凸多边形中的同一类型的单调段有关。该算法充分地利用了凸多边形顶点的有序性,使算法的时间复杂度达到最小。     

平面点集凸壳的一种近似算法

提出了一种计算海量平面点集凸壳的快速近似算法——点集坐标旋转法(PSCR)。该算法采用点集不断旋转并求X(Y)坐标极值的方法得到平面点集的近似凸壳。它充分利用了成熟的数据库技术,能够在比较短的时间内计算出海量平面点集的近似凸壳。它不需要空间索引的支持,并能获得比较理想的近似效果。     

A method for solving the n-dimensional convex hull problem

A method is presented for finding all vertices and all hyperplanes containing the faces of a convex polyhedron spanned by a given finite set X in Euclidean space Eⁿ. The present paper indicates how this method can be applied to the investigation of linear separability of two given finite sets X₁ and X₂ in Eⁿ. In the case of linear separability of these sets the proposed method makes it possible to find the separating hyperplane.