A new algorithm for computing the convex hull of a planar point set

When the edges of a convex polygon are traversed along one direction,the interior of the convex polygon is always on the same side of the edges. Based on this characteristic of convex polygons,a new algorithm for computing the convex hull of a simple polygon is proposed in this paper,which is then extended to a new algorithm for computing the convex hull of a planar point set. First,the extreme points of the planar point set are found,and the subsets of point candidate for vertex of the convex hull between extreme points are obtained. Then,the ordered convex hull point sequences between extreme points are constructed separately and concatenated by removing redundant extreme points to get the convex hull. The time complexity of the new planar convex hull algorithm is O(nlogh) ,which is equal to the time complexity of the best output-sensitive planar convex hull algorithms. Compared with the algorithm having the same complexity,the new algorithm is much faster.

Drug discrimination of Near Infrared spectroscopy based on the scaled convex hull classifier

Near Infrared spectroscopy(NIRS)has been widely used in the discrimination(classification)of pharmaceutical drugs.In real applications,however,the class imbalance of the drug samples,i.e.,the number of one drug sample may be much larger than the number of the other drugs,deceasesdrastically the discrimination performance of the classification models.To address this classimbalance problem,a new computational method--the scaled convex hull(SCH)-basedmaximum margin classifier is proposed in this paper.By a suitable selection of the reductionfactor of the SCHs generated by the two classes of drug samples,respectively,the maximalmargin classifier bet ween SCHs can be constructed which can obtain good classification per-formance.With an optimization of the parameters involved in the modeling by Cuckoo Search,a satisfied model is achieved for the classification of the drug.The experiments on spectra samplesproduced by a pharmaceutical company show that the proposed method is more effective androbust than the existing ones.

Secure planar convex hull protocol for large-scaled point sets in semi-honest model

Efficiency and scalability are still the bottleneck for secure multi-party computation geometry （SMCG）. In this work a secure planar convex hull （SPCH） protocol for large-scaled point sets in semi-honest model has been proposed efficiently to solve the above problems. Firstly, a novel priva- cy-preserving point-inclusion （PPPI） protocol is designed based on the classic homomorphic encryp- tion and secure cross product protocol, and it is demonstrated that the complexity of PPPI protocol is independent of the vertex size of the input convex hull. And then on the basis of the novel PPPI pro- tocol, an effective SPCH protocol is presented. Analysis shows that this SPCH protocol has a good performance for large-scaled point sets compared with previous solutions. Moreover, analysis finds that the complexity of our SPCH protocol relies on the size of the points on the outermost layer of the input point sets only.

A novel method for virtual clearance computation of high-speed train based on model integration and convex hull

The 3D clearance of a high-speed train(HST) is critical to ensure the safety of railway transportation. Many studies have been conducted on the inspection of the clearance profile in railway operation based on the vision system, but few researchers have focused on the computation of the 3D clearance in the design phase of an HST. This paper summarizes the virtual 3D clearance computation of an HST based on model integration and the convex hull method. First, both the aerodynamic and kinetic analysis models of the HST are constructed. The two models are then integrated according to the corresponding relationship map, and an array of transformation matrixes of the HST is created to drive the designed model simulating the physical railway motion. Furthermore, the convex hull method is adopted to compute the 3D envelope of the moving train. Finally, the Hausdorff metric is involved in the measurement of the minimum clearance model and the 3D envelope model. In addition, the color map of the Hausdorff distance is established to verify that the designed shape of the HST meets the national standards. This paper provides an effective method to accurately calculate the 3D clearance for the shape design of an HST, which greatly reduces the development cost by minimizing the physical prototype that must be built.

On Constructing Approximate Convex Hull

The algorithms of convex hull have been extensively studied in literature, principally because of their wide range of applications in different areas. This article presents an efficient algorithm to construct approximate convex hull from a set of n points in the plane in O(n+k) time, where k is the approximation error control parameter. The proposed algorithm is suitable for applications preferred to reduce the computation time in exchange of accuracy level such as animation and interaction in computer graphics where rapid and real-time graphics rendering is indispensable.

Group Target Tracking in WSN Based on Convex Hulls Merging

When a mass of individual targets move closely, it is unpractical or unnecessary to localize and track every specific target in wireless sensor networks (WSN). However, they can be tracked as a whole by view of group target. In order to decrease the amount of energy spent on active sensing and communications, a flexible boundary detecting model for group target tracking in WSN is proposed, in which, the number of sensors involved in target tracking is adjustable. Unlike traditional one or multiple individual targets, the group target usually occupies a large area. To obtain global estimated position of group target, a divide-merge algorithm using convex hull is designed. In this algorithm, group target’s boundary is divided into several small pieces, and each one is enclosed by a convex hull which is constructed by a cluster of boundary sensors. Then, the information of these small convex hulls is sent back to a sink. Finally, big convex hull merged from these small ones is considered as the group target’s contour. According to our metric of precision evaluation, the simulation experiments confirm the efficiency and accuracy of this algorithm.

Convex Hull Based Economic Operating Region for Power Grids Considering Uncertainties of Renewable Energy Sources

The increasing integration of renewable energy sources(RESs)presents significant challenges for the safe and economical operation of power grids.Addressing the critical need to assess the effect of RES uncertainties on optimal scheduling schemes(OSSs),this paper introduces a convex hull based economic operating region(CH-EOR)for power grids.The CHEOR is mathematically defined to delineate the impact of RES uncertainties on power grid operations.We propose a novel approach for generating the CH-EOR,enhanced by a big-M preprocessing method to improve the computational efficiency.Performed on four test systems,the proposed big-M preprocessing method demonstrates notable advancements:a reduction in average operating costs by over 10%compared with the box-constrained operating region(BC-OR)derived from robust optimization.Furthermore,the CH-EOR occupies less than 11.79%of the generators'adjustable region(GAR).Most significantly,after applying the proposed big-M preprocessing method,the computational efficiency is improved over 17 times compared with the traditional big-M method.

A quantum search algorithm of two-dimensional convex hull

Despite the rapid development of quantum research in recent years,there is very little research in computational geometry.In this paper,to achieve the convex hull of a point set in a quantum system,a quantum convex hull algorithm based on the quantum maximum or minimum searching algorithm(QUSSMA)is proposed.Firstly,the novel enhanced quantum representation of digital images is employed to represent a group of point set,and then the QUSSMA algorithm and vector operation are used to search the convex hull of the point set.In addition,the algorithm is simulated and compared with the classical algorithm.It is concluded that the quantum algorithm accelerates the classical algorithm when the Mpvalue of the convex hull point is under a certain condition.

Convex hull theorem for multiply connected domains in the plane with an estimate of the quasiconformal constant

For any multiply connected domain Ω in ?2, let S be the boundary of the convex hull in H 3 of ?2Ω which faces Ω. Suppose in addition that there exists a lower bound l > 0 of the hyperbolic lengths of closed geodesics in Ω. Then there is always a K-quasiconformal mapping from S to Ω, which extends continuously to the identity on ?S = ?Ω, where K depends only on l. We also give a numerical estimate of K by using the parameter l.

Convex hull of set in thick part of Teichmller space

Let X be a non-elementary Riemann surface of type(g,n),where g is the number of genus and n is the number of punctures with 3g-3+n>1.Let T(X)be the Teichmller space of X.By constructing a certain subset E of T(X),we show that the convex hull of E with respect to the Teichmller metric,the Carathodory metric and the Weil-Petersson metric is not in any thick part of the Teichmler space,respectively.This implies that convex hulls of thick part of Teichmller space with respect to these metrics are not always in thick part of Teichmller space,as well as the facts that thick part of Teichmller space is not always convex with respect to these metrics.

无线传感器网络中基于Convexhull的能量空洞避免路由算法

提供了一种绕过无线传感器网络"能量空洞"的方法(CHA方法),可以用来找到绕过能量空洞的最优节点路由路径。在数据包从源节点传递到目的节点的过程中,通过遇到能量空洞,先勾勒出空洞范围,再基于凸壳(Convex hull)找到绕过能量空洞的最优节点路由路径。仿真结果表明,该算法优化了能量空洞绕洞路由路径,有效提高了无线传感器网络传输效率,减少了无线传感器能量损耗和信息传递的延迟。

On Fuzzy Simplex and Fuzzy Convex Hull

In this paper, we discuss fuzzy simplex and fuzzy convex hull, and give several representation theorems for fuzzy simplex and fuzzy convex hull. In addition, by giving a new characterization theorem of fuzzy convex hull, we improve some known results about fuzzy convex hull.

Determination of the nucleotide or amino acid composition of genome or protein sequences by using natural vector method and convex hull principle

Although with the continuous development of sequencing technology,the number of genome and protein sequences has grown rapidly,these sequences are only a small part of nature.Biologically,it is still a challenging and important problem to detect and predict some new genome or protein sequences based on real sequence data,which motivates us to solve the problem mathematically.The first step to predict the new sequences is determining the nucleotide or amino acid composition of them.In this paper,we apply natural vector method and convex hull principle to determine the nucleotide or amino acid composition of new genome or protein sequences.Our algorithm is based on optimization strategy.The SARS-CoV-2 genome and protein datasets are used to verify the feasibility of our algorithm.Numerical experiments show that our algorithm can detect and predict possible number of each nucleotide or amino acid of genome and protein sequence with respect to the second order natural vectors.

A New Representation and Algorithm for Constructing Convex Hulls in Higher Dim ensional Spaces

This paper presents a new and simple scheme to describe the convex hull in R^d,which only uses three kinds of the faces of the convex hull,i.e.,the d-1-faces,d-2-faces and 0-faces.Thus,we develop an efficient new algorithm for constructing the convex hull of a finite set of points incrementally. This algorithm employs much less storage and time than that of the previously-existing approaches.The analysis of the running time as well as the storage for the new algorithm is also theoretically made.The algorithm is optimal in the worst case for even d.

A NEW CONVEX HULL ALGORITHM FOR ANY POLYGON

A new algorithm for finding convex hull of a polygon is proposed. An example is given to show the effectiveness and the simplicity of the algorithm.

基于机器视觉的芯片字符区域分割和定位算法

芯片表面的字符对分选具有重要意义,对字符的定位是分选工作的关键步骤。为了提高分选工作定位效率和定位精度,提出了一种基于改进的区域生长算法和凸包检测算法分割和定位芯片表面字符区域方法。首先,对采集图像进行预处理操作,利用改进的Canny算法获取无干扰图像边缘,将图像边缘作为区域生长法的种子点并以图像自适应阈值作为生长准则分割图像,使用最大内接矩形算法粗定位字符区域;其次,采用Harris角点检测算法获取字符角点分布位置;最后,筛选角点并提取关键点,利用一种改进的凸包检测算法定位字符区域。经过实验验证,所设计的算法能够完整的分割和定位芯片表面字符区域,定位精度和效率较原有方法提升5.3%和15.4%,满足实际工业生产的要求。

A COUNTER－EXAMPLE TO A FAST ALGORITHM FOR FINDING THE CONVEX HULL OF A SIMPLE POLYGON

A linear-time algorithm was recently published (International Conference Proceedings ofPacific Graphics' 94/CADDM' 94, August 26-29 , 1994 , Beijing , China) for computing the convexhull of a simple polygon. In this note we present a counter-example to that algorithm by exhibiting afamily of polygons for which the algorithm discards vertices that are on the convex hull.

基于凸包算法的极端运行方式提取方法

在电力系统规划与运行的安全稳定计算中,一般选择对安全稳定最不利的运行方式进行校验,但随着新能源渗透率的增加,电网越发复杂多变,人工选择场景主观性较强,针对此问题,提出了一种基于快速凸包算法的极端运行方式提取,从而满足场景选取进行安全校核需求。从电源规划、发输电协调规划两个角度,考虑发电充裕性、火电爬坡需求、网络传输安全3个方面,分析影响规划的极端运行方式;基于凸包算法分别从上述3个方面构建坐标系进行极端运行方式提取;采用中国西北地区电网为算例进行极端运行方式提取,并与基于K-means算法的极端场景提取做对比,结果表明:所提方法能为场景选取提供有效数据支撑,满足电网规划要求。

一种基于流形的机械臂动作构型知识压缩表达方法

针对在机械臂分拣任务中,存在物体形状各异、大小不一、训练神经网络成本过高的问题,提出一种基于流形空间的机械臂快速分拣方法。通过自主设计的一款简易实验装置模拟代替机械臂进行实验。对高维数据进行压缩,结合三维快速凸包求解算法,对体积大小不同的同类物体的流形空间进行分割,以凸包形式将稳定性较高的点集包裹起来。实验结果表明,体积大小不同的同类物体的高稳定流形子空间是一致的。该方法可以通过对一种物体的流形子结构进行尺度放缩,得到不同大小的同类物体的高稳定分拣区域,用于生成高效、可靠的机械臂分拣任务中的6D位姿构型,以提高分拣作业的工作效率。

基于改进凸包缺陷算法的扎带定位方法

针对传统视觉在检测捆扎带时存在难检、漏检、定位扎带位置困难和速度慢等问题,提出一种基于改进凸包缺陷算法的扎带定位方法。采用自适应直方图均衡化图像增强算法,以增强编织袋区域与背景的对比度;利用快速凸包算法获得编织袋轮廓的凸包,减少获取凸包的时间;最后,通过改进凸包缺陷算法对编织袋轮廓凸包进行缺陷检测,根据检测结果中凸包缺陷点的位置和缺陷深度进行筛选得到扎带定位点。同时为验证该算法的准确性与鲁棒性,在具有复杂背景干扰的环境下进行实验,将传统凸包缺陷算法与改进后的凸包缺陷算法进行对比分析。实验结果表明:相比于传统凸包缺陷算法无法检测出编织袋轮廓的全部缺陷从而存在漏检,改进后的凸包缺陷算法漏检率为0,定位误差小于4 mm,可有效定位扎带位置并具有较高的鲁棒性。