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.

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.

基于重构级别辨识的主配协同鲁棒供电恢复方法

传统配电网供电恢复策略大多先进行孤岛划分、后进行动态重构,缺少对二者的共同考虑,而全局重构又存在经济性差、操作难度大等问题。为此,提出基于重构级别辨识的主配协同鲁棒供电恢复方法。首先,根据配电系统的故障情况,按照局部自治、低级别优先重构的原则,快速确定主(变电站层级)、配(配电线路层级)多级重构需求。然后,对不同级别的区域进行孤岛划分与重构。接着,针对描述分布式光伏出力不确定性的凸包多面体集合存在放缩过程中保守性大的问题,采用超平面方法切割凸包集合并建立改进凸包集合模型。进一步,构建了配电网鲁棒供电恢复模型,并采用列与约束生成算法对鲁棒供电恢复模型进行求解。最后,通过改进的78节点系统进行仿真验证。结果表明,基于重构级别辨识的主配协同鲁棒供电恢复方法可以降低保守性,提高供电恢复结果的鲁棒性。

采用Hull树的贪婪地理位置路由算法的设计

地理位置路由算法是指借助节点获得的地理位置信息进行无线传感网络中的路由发现与数据转发工作。本文提出一种基于Hull树的贪婪地理位置路由算法——Greedy Hull Tree Geographic Routing(GHTGR)。通过图形学中凸包的概念,在网络初始阶段分布式地在各节点上建立Hull树以探查网络局部拓扑结构;同时在数据分组的路由转发阶段,通过Hull树内的搜索,寻找下一跳转发节点,完成数据分组的转发传输。通过仿真实验表明,与现有地理位置路由算法相比,该算法能够正确地寻找数据转发路径,有效地减少网络能耗,提高网络传输性能。

基于正常工作区的凝汽器多变量报警监测

凝汽器作为电厂的重要设备之一,保证凝汽器工作状态的稳定性对发电机组的安全经济运行具有重要意义,因此提出了一种基于正常工作区的凝汽器多变量报警监测方法。首先,根据凝汽器的热力特性搭建仿真模型,计算出模型中关联变量的解析解。然后,从历史数据中提取凝汽器真空及其关联变量的有效数据,利用遗传算法对模型的未知参数进行辨识。最后,以系统机理模型中多个关联变量的正常数据点为基础,建立相关关联变量的正常工作区。基于工业案例的测试结果验证了所提方法能够有效监测凝汽器系统,使操作人员提前发现异常情况,为火电机组的可靠运行提供了保障。

塞罕坝华北落叶松树冠投影面积模型构建

依据河北省塞罕坝国家森林公园华北落叶松纯林12块标准地4个不同林龄(10、15、20、25 a)数据,使用圆形、椭圆形、矩形和凸包结构,分别在4点位和8点位计算树冠投影面积,并分析不同计算方法和林龄之间的差异。通过绘制12个变量的散点图和相关性图,分析变量对树冠投影面积的影响。利用全子集法和刀切法构建树冠投影面积预测模型。结果表明,8点位的计算精度优于4点位,且15 a林龄的树冠投影面积存在显著变异趋势。最终,胸径(DBH)、单木竞争因子(BALD)、相对直径(RD)、冠长(CL)和冠幅(Crown)被纳入模型,除竞争因子外,其他变量与树冠投影面积呈显著正相关。