Search

A wordxthat is absent from a wordyis calledminimalif all its proper factors occur iny. Given a collection ofkwordsy1, … ,ykover an alphabetΣ, we are asked to compute the set$\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$M{y1,…,yk}ℓof minimal absent words of length at mostℓof the collection {y1, … ,yk}. The set$\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$M{y1,…,yk}ℓcontains all the wordsxsuch thatxis absent from all the words of the collection while there existi,j, such that the maximal proper suffix ofxis a factor ofyiand the maximal proper prefix ofxis a factor ofyj. In data compression, this corresponds to computing the antidictionary ofkdocuments. In bioinformatics, it corresponds to computing words that are absent from a genome ofkchromosomes. Indeed, the set$\mathrm {M}^{\ell }_{y}$Myℓof minimal absent words of a wordyis equal to$\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$M{y1,…,yk}ℓfor any decomposition ofyinto a collection of wordsy1, … ,yksuch that there is an overlap of length at leastℓ− 1 between any two consecutive words in the collection. This computation generally requiresΩ(n) space forn= |y| using any of the plenty available$\mathcal {O}(n)$O(n)-time algorithms. This is because anΩ(n)-sized text index is constructed overywhich can be impractical for largen. We do the identical computation incrementally using output-sensitive space. This goal is reasonable when$\| \mathrm {M}^{\ell }_{\{y_1,\ldots ,y_N\}}\| =o(n)$∥M{y1,…,yN}ℓ∥=o(n), for allN∈ [1,k], where ∥S∥ denotes the sum of the lengths of words in setS. For instance, in the human genome,n≈ 3 × 109but$\| \mathrm {M}^{12}_{\{y_1,\ldots ,y_k\}}\| \approx 10^{6}$∥M{y1,…,yk}12∥≈106. We consider a constant-sized alphabet for stating our results. We show thatall$\mathrm {M}^{\ell }_{y_{1}},\ldots ,\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$My1ℓ,…,M{y1,…,yk}ℓcan be computed in$\mathcal {O}(kn+{\sum }^{k}_{N=1}\| \mathrm {M}^{\ell }_{\{y_1,\ldots ,y_N\}}\| )$O(kn+∑N=1k∥M{y1,…,yN}ℓ∥)total time using$\mathcal {O}(\textsc {MaxIn}+\textsc {MaxOut})$O(MaxIn+MaxOut)space, where MaxIn is the length of the longest word in {y1, … ,yk} and$\textsc {MaxOut}=\max \limits \{\| \mathrm {M}^{\ell }_{\{y_1,\ldots ,y_N\}}\| :N\in [1,k]\}$MaxOut=max{∥M{y1,…,yN}ℓ∥:N∈[1,k]}. Proof-of-concept experimental results are also provided confirming our theoretical findings and justifying our contribution.

We consider the directed Steiner network problem, where given a weighted directed graph [Formula: see text] and [Formula: see text] pairs of vertices [Formula: see text], one has to find the minimum weight subgraph [Formula: see text] of [Formula: see text] that contains path from [Formula: see text] to [Formula: see text] for all [Formula: see text]. We search for the main cause of the complexity of the problem and introduce the notions of junction vertex and shared segment in an optimal solution. We study the parameterized complexity of the problem with respect to these parameters and achieve several parameterized hardness results. Also, we present two output-sensitive algorithms for the problem, which are much simpler and easier to implement than the previously best known one; and in addition, when the paths corresponding to the input pairs have few shared vertices or arcs in the optimal solution, these algorithms outperform the previous one.

Reducing samples through convex hull vertices selection (CHVS) within each class is an important and effective method for online classification problems, since the classifier can be trained rapidly with the selected samples. However, the process of CHVS is NP-hard. In this paper, we propose a fast algorithm to select the convex hull vertices, based on the convex hull decomposition and the property of projection. In the proposed algorithm, the quadratic minimization problem of computing the distance between a point and a convex hull is converted into a linear equation problem with a low computational complexity. When the data dimension is high, an approximate, instead of exact, convex hull is allowed to be selected by setting an appropriate termination condition in order to delete more nonimportant samples. In addition, the impact of outliers is also considered, and the proposed algorithm is improved by deleting the outliers in the initial procedure. Furthermore, a dimension convention technique via the kernel trick is used to deal with nonlinearly separable problems. An upper bound is theoretically proved for the difference between the support vector machines based on the approximate convex hull vertices selected and all the training samples. Experimental results on both synthetic and real data sets show the effectiveness and validity of the proposed algorithm.

We design a new algorithm, called Incremental Enumeration (IncEnu), for the enumeration of full-dimensional cells of hyperplane arrangements (or dually, for the enumeration of vertices of generator...

In this paper, we propose an arc-search interior-point algorithm for convex quadratic programming with a wide neighborhood of the central path, which searches the optimizers along the ellipses that approximate the entire central path. The favorable polynomial complexity bound of the algorithm is obtained, namely O(nlog((x0)Ts0/e)) which is as good as the linear programming analogue. Finally, the numerical experiments show that the proposed algorithm is efficient.

Bounding hulls such as convex hull, -shape, -hull, concave hull, crust, etc. offer a wide variety of useful applications. In this paper, we explore another bounding hull, namely -concave hull, as a generalization of convex hull. The parameter determines the smoothness level of the constructed hull on a set of points. We show that it is NP-hard to compute -concave hull on a set of points for any 0<

This paper proposes a branch-and-bound algorithm for solving the unit-modulus constrained complex quadratic programming problems (CQPP). We study the convex hull of a unit-modulus complex variable with argument constraints, derive new valid linear inequalities from the convex hull, construct an improved semidefinite relaxation of CQPP, and then design an efficient algorithm for solving CQPP globally. The proposed algorithm branches on the sets of argument constraints and derives new valid inequalities from the partitioned sets of arguments. Numerical results are included to support the effectiveness of the proposed algorithm for finding a global solution to CQPP.

Designing an algorithm to deal with a convex shape is easier than that for a concave shape. Efficient algorithms are required to process concave shapes, because every application does not deal with convex shapes. An alternative approach is to first transform a concave shape into a set of convex shapes so that efficient algorithms available for convex shapes can be utilized. This paper proposes an algorithm for partitioning a concave polygon into smaller number of convex pieces. Each resultant convex piece then can be processed using a simple algorithm applicable to convex shapes. In this way, any arbitrary shape can be processed using such simple algorithms with the aid of the proposed algorithm. There are plenty of algorithms available in literature to solve convex partitioning problem. Hertel Mehlhorn algorithm is the most efficient algorithm, but it does not minimize the number of convex pieces satisfactorily. Further the Hertel Mehlhorn algorithm is the minimum memory consuming algorithm available in literature. Later Geene proposed an algorithm which gives the minimum number of convex pieces. It uses dynamic programming technique and needs high amount of memory. Therefore Geene’s algorithm is not suitable for systems where the memory is limited. Chazelle proposed an efficient algorithm which gives minimum number of convex pieces. However a data structure to implement Chazelle’s algorithm is not available in literature. The experimental results showed that the proposed algorithm gives smaller number of convex pieces than the Hertel Mehlhorn algorithm. The memory consumption of the proposed algorithm is also lower than the Hertel Mehlhorn algorithm.

This study proposes an algorithm to solve inverse reliability problems with a single unknown parameter. The proposed algorithm is based on an existing algorithm, the inverse first-order reliability method (inverse-FORM), which uses the Hasofer Lind Rackwitz Fiessler (HLRF) algorithm. The initial algorithm analyzed in this study was developed by modifying the HLRF algorithm in inverse-FORM using the Broyden-Fletcher-Goldarb-Shanno (BFGS) update formula completely. Based on numerical experiments, this modification was found to be more efficient than inverse-FORM when applied to most of the limit state functions considered in this study, as it requires comparatively a smaller number of iterations to arrive at the solution. However, to achieve this higher computational efficiency, this modified algorithm sometimes compromised the accuracy of the final solution. To overcome this drawback, a hybrid method by using both the algorithms, original HLRF algorithm and the modified algorithm with BFGS update formula, is proposed. This hybrid algorithm achieves better computational efficiency, compared to inverse-FORM, without compromising the accuracy of the final solution. Comparative numerical examples are provided to demonstrate the improved performance of this hybrid algorithm over that of inverse-FORM in terms of accuracy and efficiency.

The convex hull of a set of points, $C$, serves to expose extremal properties of $C$ and can help identify elements in $C$ of high interest. For many problems, particularly in the presence of noise, the true vertex set (and facets) may be difficult to determine. One solution is to expand the list of high interest candidates to points lying near the boundary of the convex hull. We propose a quadratic program for the purpose of stratifying points in a data cloud based on proximity to the boundary of the convex hull. For each data point, a quadratic program is solved to determine an associated weight vector. We show that the weight vector encodes geometric information concerning the point's relationship to the boundary of the convex hull. The computation of the weight vectors can be carried out in parallel, and for a fixed number of points and fixed neighborhood size, the overall computational complexity of the algorithm grows linearly with dimension. As a consequence, meaningful computations can be complete...

A linear-time algorithm for determining the triangular hull of a digital object that is digitized with a uniform triangular-grid scan, is presented in this paper. A triangular hull consists of a sequence of edges on the underlying triangular grid T consisting of three sets of parallel grid lines that are inclined at 0 ° , 60 ° , and 120 ° w.r.t. the x -axis. The proposed algorithm determines the triangular hull of a given object on the basis of certain geometrical properties of the edge-sequence observed along its boundary. The approach is purely combinatorial in nature as opposed to other conventional algorithms used for computing the convex hull such as those based on divide-and-conquer or line-sweep. The running time of the algorithm is linear on the number of pixels on the perimeter of the object. Also, by using a more sparse grid, i.e., by increasing the grid unit, the number of perimeter-pixels, and in turn, the running time of the algorithm can be reduced proportionately. The algorithm is tested extensively on several test cases and experimental results and analysis are presented.

String covers are a powerful tool for analyzing the quasi-periodicity of 1-dimensional data and find applications in automata theory, computational biology, coding and the analysis of transactional data. A cover of a string T is a string C for which every letter of T lies within some occurrence of C. String covers have been generalized in many ways, leading to k-covers, \(\lambda \)-covers, approximate covers and were studied in different contexts such as indeterminate strings.

We consider packing axis-aligned rectangles r 1 , … , r n in the unit square [ 0 , 1 ] 2 such that a vertex of each rectangle r i is a given point p i (i.e., r i is anchored at p i ). We explore the combinatorial structure of all locally maximal configurations. When the given points are the lower-left corners of the rectangles, the number of maximal packings is shown to be at most 2 n C n , where C n is the nth Catalan number. The number of maximal packings remains exponential in n when the points may be arbitrary corners of the rectangles. Both upper bounds are complemented with exponential lower bounds. Finally, we define the graph of all lower-left anchored maximal rectangle packings, where the edges correspond to elementary operations between two packings, which leads to an output sensitive algorithm for computing these packings.

The dual problem of one-class support vector machine (OCSVM) can be interpreted as a minimum norm problem associated with the reduced convex hull. Based on this geometric interpretation, a generalized Mitchell-Dem'yanov-Malozemov (GMDM) algorithm is proposed for OCSVM. The GMDM algorithm finds the minimum norm point in the reduced convex hull of training samples and employs such a point to construct the separating hyper-plane. Numerical experiments are conducted to compare the proposed geometric algorithm with some existing algorithms such as two modified sequential minimal optimization algorithms and the generalized Gilbert algorithm. The experimental results show that the GMDM algorithm exhibits better performance in terms of computational efficiency while achieving comparable classification accuracies to other algorithms.

A second-order learning algorithm based on differential geometry is used to numerically solve the linear matrix equation Q = x + ∑ i = 1 m A i T x A i − ∑ i = 1 n B i T x B i . An extended Hamiltonian algorithm is proposed based on the manifold of symmetric positive definite matrices. The algorithm is compared with traditional coupled fixed-point algorithm. Numerical experiments illustrate that the convergence speed of the provided algorithm is faster than that of the coupled fixed-point algorithm.

A novel predictive measure that predicts which algorithm is best at any given point in time. Always select the predicted best algorithm to run for the next generation.The performance of our method is very competitive if viewed as another novel "individual" algorithm.A very interesting positive synergistic effect is found between algorithms in our method.A novel performance evaluation method that makes a lot of sense when one has an absolute maximum number of function evaluations allowed in your application.Application on a Heating Ventilation and Air Conditioning design problem demonstrates that the method can be used to solve real world problems with constraints and that it performs better than choosing an algorithm randomly. Many good evolutionary algorithms have been proposed in the past. However, frequently, the question arises that given a problem, one is at a loss of which algorithm to choose. In this paper, we propose a novel algorithm portfolio approach to address the above problem for single objective optimization. A portfolio of evolutionary algorithms is first formed. Covariance Matrix Adaptation Evolution Strategy (CMA-ES), History driven Evolutionary Algorithm (HdEA), Particle Swarm Optimization (PSO2011) and Self adaptive Differential Evolution (SaDE) are chosen as component algorithms. Each algorithm runs independently with no information exchange. At any point in time, the algorithm with the best predicted performance is run for one generation, after which the performance is predicted again. The best algorithm runs for the next generation, and the process goes on. In this way, algorithms switch automatically as a function of the computational budget. This novel algorithm is named Multiple Evolutionary Algorithm (MultiEA). The predictor we introduced has the nice property of being parameter-less, and algorithms switch automatically as a function of budget. The following contributions are made: (1) experimental results on 24 benchmark functions show that MultiEA outperforms (i) Multialgorithm Genetically Adaptive Method for Single Objective Optimization (AMALGAM-SO); (ii) Population-based Algorithm Portfolio (PAP); (iii) a multiple algorithm approach which chooses an algorithm randomly (RandEA); and (iv) a multiple algorithm approach which divides the computational budget evenly and execute all algorithms in parallel (ExhEA). This shows that it outperforms existing portfolio approaches and the predictor is functioning well. (2) Moreover, a neck to neck comparison of MultiEA with CMA-ES, HdEA, PSO2011, and SaDE is also made. Experimental results show that the performance of MultiEA is very competitive. In particular, MultiEA, being a portfolio algorithm, is sometimes even better than all its individual algorithms, and has more robust performance. (3) Furthermore, a positive synergic effect is discovered, namely, MultiEA can sometimes perform better than the sum of its individual EAs. This gives interesting insights into why an algorithm portfolio is a good approach. (4) It is found that MultiEA scales as well as the best algorithm in the portfolio. This suggests that MultiEA scales up nicely, which is a desirable algorithmic feature. (5) Finally, the performance of MultiEA is investigated on a real world problem. It is found that MultiEA can select the most suitable algorithm for the problem and is much better than choosing algorithms randomly.

Recently we developed a Bayesian-FBP (Filtered Backprojection) algorithm for CT image reconstruction. This algorithm is also referred to as the FBP-MAP (FBP Maximum a Posteriori) algorithm. This non-iterative Bayesian algorithm has been applied to real-time MRI, in which the k-space is under-sampled. This current paper investigates the possibility to extend this Bayesian-FBP algorithm by introducing more controlling parameters. Thus, our original Bayesian-FBP algorithm became a special case of the extended Bayesian-FBP algorithm. A cardiac patient data set is used in this paper to evaluate the extended Bayesian-FBP algorithm, and the result from a well-establish iterative algorithm with ${{\rm L}_1}$ -norms is used as the gold standard. If the parameters are selected properly, the extended Bayesian-FBP algorithm can outperform the original Bayesian-FBP algorithm.

Computing the convex hull of a set of points is a fundamental operation in many research fields, including geometric computing, computer graphics, computer vision, robotics, and so forth. This problem is particularly challenging when the number of points goes beyond some millions. In this article, we describe a very fast algorithm that copes with millions of points in a short period of time without using any kind of parallel computing. This has been made possible because the algorithm reduces to a sorting problem of the input point set, what dramatically minimizes the geometric computations (e.g., angles, distances, and so forth) that are typical in other algorithms. When compared with popular convex hull algorithms (namely, Graham's scan, Andrew's monotone chain, Jarvis' gift wrapping, Chan's, and Quickhull), our algorithm is capable of generating the convex hull of a point set in the plane much faster than those five algorithms without penalties in memory space. We propose a 2D convex hull algorithm based on comparison operators.We propose a 2D convex hull algorithm that outperforms Quickhull.We propose a 2D non-convex hull algorithm.

Algorithm for computing the convex hull of a set of points in E3 we are proposed.The algorithm is based on spherical space subdivision.The algorithm eliminates as many input points as possible before the convex hull calculation.Experimental results show that the proposed algorithm achieves a better time complexity in comparison with other algorithms in E3. Convex hulls are fundamental geometric tools used in a number of algorithms. This paper presents a fast, simple to implement and robust Smart Convex Hull (S-CH) algorithm for computing the convex hull of a set of points in E3. This algorithm is based on "spherical" space subdivision. The main idea of the S-CH algorithm is to eliminate as many input points as possible before the convex hull construction. The experimental results show that only a very small number of points are used for the final convex hull calculation. Experiments made also proved that the proposed S-CH algorithm achieves a better time complexity in comparison with other algorithms in E3.

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).

Correlating a thermal model could be a challenging problem in global optimization, which often requires employing a genetic algorithm. This work studies choosing the optimal set of the genetic algorithm control parameters when it is used for this purpose. Two practical thermal models are considered. For the small model the optimal set of the genetic algorithm parameters was found by applying a double genetic algorithm where the outer algorithm tried to minimize the best fitness value achieved by the inner one by varying the inner algorithm control parameters. In addition, it was demonstrated that in a practical calculation increasing the population size can easily result in a worse accuracy. The proper choice of the population size was studied for the large model. The double genetic algorithm was modified by starting each run of the inner algorithm with the best solution obtained until then, instead of using the same initial population in all the runs. Doing all the runs with the same population size and ...

This paper provides a polynomial-time algorithm for economic lot-sizing problems with convex costs in the production and inventory quantities. The resulting algorithm is based on a primal-dual approach that takes advantage of the problem's special structure. This approach improves upon existing results in the literature, which are either pseudo-polynomial or focus on special cases. We apply the approach to a production planning problem with price-dependent supply, leading to an improved bound on the algorithm's running time for a special case.

A quick convex hull building algorithm using grid and binary tree is proposed for the minimum convex buidling of planar point set. Grids are used to assess and eliminate those interior points wihtout any contribution to convex hull building and points are sought in the boundary grid only so as to enhance the efficiency of algorithm. The minimum convex bull is built by taking such advantages of binary tree as quick, convenient and applicable for various point sets with different distributions, so as to resolve the description problem of concave point. The time complexity of the algorithm is low because of grid pretreatment. As the results of comparative expriment of random point and actual picture show, the proposed algorithm can obtain the best profile of 2D planar picture with minimum time, which is applicable for describing the shape of irregular convex-concave objects.

The convex hull of a set of two-dimensional points, $P$ , is the minimal convex polygon that contains all the points in $P$ . Convex hull is important in many applications such as GIS, statistical analysis and data mining. Due to the ubiquity of data uncertainty such as location uncertainty in real-world applications, we study the concept of convex hull over uncertain data in 2D space. We propose the Probabilistic Convex Hull (PCH) query and demonstrate its applications, such as Flickr landscape photo extraction and activity region visualization, where location uncertainty is incurred by GPS devices or sensors. To tackle the problem of possible world explosion, we develop an $O(N^3)$ algorithm based on geometric properties, where $N$ is the data size. We further improve this algorithm with spatial indices and effective pruning techniques, which prune the majority of data instances. To achieve better time complexity, we propose another $O(N^2\,\log\, N)$ algorithm, by maintaining a probability oracle in the form of a circular array with nice properties. Finally, to support applications that require fast response, we develop a Gibbs-sampling-based approximation algorithm which efficiently finds the PCH with high accuracy. Extensive experiments are conducted to verify the efficiency of our algorithms for answering PCH queries.

The recently proposed function controlled variable step-size least-mean-square (FCVSSLMS) algorithm has shown high performance in different noise environments. The performance of the algorithm can be improved further if the system is sparse. In this paper, we propose a new algorithm based on the FCVSSLMS algorithm. The proposed algorithm imposes an approximate penalty in the cost function of the FCVSSLMS algorithm. We also present the convergence analysis of the proposed algorithm and derive the stability criterion. The performance of the proposed algorithm is compared to those of the variable step-size least-mean-square, more robust variable step-size least-mean-square, FCVSSLMS algorithm and reweighted zero-attracting least-mean-square algorithm in a system identification setting with an additive white Gaussian noise and additive correlated Gaussian noise. The proposed algorithm has shown high performance compared to the others in terms of the convergence rate and mean square deviation.

In critical event (e.g., fire or gas) monitoring applications of wireless sensor networks (WSNs), convex hull of the event region is an efficient tool in handling the usual tasks like event report, routes reconstruction and human motion planning. Existing works on estimating convex hull of event region usually require location information of sensor nodes, which needs high communication cost or hardware cost. In this paper, to avoid the requirement of location information, we define topological convex hull (T-convex hull) which presents the convex contour of an event region directly with a route passing by nodes, and hence becomes more efficient in handling the above tasks. To obtain the T-convex hull of event region in the absence of locations, we propose a low-weight (in terms of computation and storage resource requirement) distributed algorithm, with which sensor nodes just need to count the hop counts from some nodes. The communication cost of the algorithm is also low and independent of the network size. Comprehensive and largescale simulations are conducted, showing the effectiveness and much lower communication cost of the proposed algorithm, compared with related method. Index Terms- Wireless sensor networks (WSNs), event region, convex hull, topological methods, the shortest path tree.

In order to obtain an orientation error of planar feature accurate, a method to evaluate it using convex hull is proposed. Firstly, a convex hull is established based on a set of measured points on the planar datum feature by the coordinate measurement machine (CMM). Then, the datum simulator is determined by the vertices of the convex hull with taking maximum material requirements (MMC) into consideration. Afterwards, allowable variation range of the locating features is derived with relative to the datum simulator. Finally, orientation error is evaluated based on convex hull constructed by measuring points of the location feature.

The anchor words algorithm performs provably efficient topic model inference by finding an approximate convex hull in a high-dimensional word co-occurrence space. However, the existing greedy algorithm often selects poor anchor words, reducing topic quality and interpretability. Rather than finding an approximate convex hull in a high-dimensional space, we propose to find an exact convex hull in a visualizable 2- or 3-dimensional space. Such low-dimensional embeddings both improve topics and clearly show users why the algorithm selects certain words.

The LMS-type algorithms are effectively used in diverse adaptive filtering applications such as; blind system identification, channel equalization, etc. For some applications such as echo cancellation, which requires a large filter length, a very long time is required to estimate the coefficients via the conventional least-mean-square (LMS) algorithm. Actually, updating the filter coefficients block by block of the input data but not for each sample of input, users can get a very fast processing time depending on the block length. Additionally, the performance of the block-LMS (BLMS) algorithm can be improved by using a variable step-size in the update equation. Also, in system identification, if the unknown system is sparse, then the performance of the algorithm can be improved further by imposing a penalty term in the cost function of the BLMS algorithm which, in turn, helps in exploiting the sparsity of the unknown system. In this paper, we investigate the performance of recently proposed BLMS-type algorithm for sparse systems. The convergence analysis of the proposed algorithm is presented for the first time. Also, the effects of the zero-attracting coefficient, ρ, and the sparsity degree on MSD have been investigated. Finally, the performance of the algorithm is compared to those of the BLMS and the other previously proposed adaptive algorithms, in terms of convergence rate and mean-square-deviation (MSD). Simulations show that the proposed algorithm guarantees better performance than the other algorithms.

In wireless sensor networks (WSNs), each sensor node can estimate the global parameter from the local data in a distributed manner. This paper proposed a robust diffusion estimation algorithm based on a minimum error entropy criterion with a self-adjusting step-size, which are referred to as the diffusion MEE-SAS (DMEE-SAS) algorithm. The DMEE-SAS algorithm has a fast speed of convergence and is robust against non-Gaussian noise in the measurements. The detailed performance analysis of the DMEE-SAS algorithm is performed. By combining the DMEE-SAS algorithm with the diffusion minimum error entropy (DMEE) algorithm, an Improving DMEE-SAS algorithm is proposed for a non-stationary environment where tracking is very important. The Improving DMEE-SAS algorithm can avoid insensitivity of the DMEE-SAS algorithm due to the small effective step-size near the optimal estimator and obtain a fast convergence speed. Numerical simulations are given to verify the effectiveness and advantages of these proposed algorithms.

Finding the polygon hull in a connected Euclidean graph can be considered as the problem of finding the convex hull with the exception that at any iteration a vertex can be chosen only if it is connected to the vertex chosen at the previous iteration. One of the methods that can be used for this kind of problems is Jarvis' algorithm which allows to find the convex hull and which must be adapted because it does not take into account the connections of the nodes. In this paper, we propose a new algorithm that chooses for a current node and among its neighbors in the graph the nearest polar angle node with respect to the node found in the previous iteration. Its complexity is O ( gh 2 ) , where g is the maximum degree of the graph and h the number of the nodes on the hull. For ease of presentation, we first identify some specific graph-structures whose presence may lead a basic version of the algorithm to fail, and we then show how to modify that version to obtain a procedure of the given complexity. Finally, we present some practical applications that can be resolved using the proposed algorithm.

This paper presents a research methodology to detect fingertips from an image which contains an outstretched hand. The research is divided into three stages. In stage one, a partitioning method is developed to perform image noise reduction. The main idea for this method is to divide the image into small pieces and analyse number of skin pixels in each piece. Image pieces which contain less density in skin pixels are considered as noise and discarded. In stage two, a new hybrid convex hull algorithm is developed to extract the convex hull vertices directly from the de-noised image in the previous stage without going through the edge detection processes. Jarvis March and Bresenham Algorithm are used to perform the extraction of seven vertices of the convex hull. In stage three, every edge of convex hull is calculated by using Distance Formula and analysed for prediction of the fingertips location. The two longest edges in the convex hull are taken as the edges connecting wrist-thumb and wrist-pinky fingers....

In this paper, a specific class of convex feasibility problems are considered and a non-interior continuation algorithm based on a smoothing function to solve this class of problems is introduced. The proposed algorithm solves at most one system of linear equations at each iteration. Under some weak assumptions, we show that the algorithm is globally linearly and locally quadratically convergent. Preliminary numerical results are also reported, which verify the favorable theoretical properties of the proposed algorithm.

An algorithm which computes the minimum area triangle enclosing a convex polygon in linear time already exists in the literature. The paper describing the algorithm also proves that the provided solution is optimal and a lower complexity sequential algorithm cannot exist. However, only a high-level description of the algorithm was provided, making the implementation difficult to reproduce. The present note aims to contribute to the field by providing a detailed description of the algorithm which is easy to implement and reproduce, and a benchmark comprising 10,000 variable sized, randomly generated convex polygons for illustrating the linearity of the algorithm.

There recently has been much interest in smoothing-type algorithms for solving the linear second-order cone programming (LSOCP). We extend such method to solve the convex second-order cone programming (CSOCP), which is an extension of the LSOCP. In this paper, we first propose a new smoothing function. Based on this function, we establish a smoothing Newton algorithm for solving the CSOCP and prove that the algorithm is globally and locally quadratically convergent under suitable assumptions. For the established algorithm, we use a generalized Armijo-type search rule to generate the step size. Some numerical results are reported which indicate the effectiveness of our algorithm.

This paper presents an enhanced version and an incremental learning version of the visual-attention-imitation convex hull algorithm reported in our latest paper in Liu et al. (2012) [3]. The enhanced algorithm merges the virtue of point comparison of the Graham scan algorithm into the visual-attention-imitation convex hull algorithm. In comparison with its previous edition, the proposed algorithm achieved a significant time saving. In view of machine learning, there are interesting situations where training data acquisition must take place over time. An incremental learning version is also proposed in this paper in order to compute convex hulls of point sets whose points are acquired over time. The incremental learning version reuses the prior results and computes the new convex hull without processing of previous points. Experimental results show that the incremental learning version is more flexible and more efficient for incremental learning tasks.

A novel three-dimensional (3D) convex hull method is proposed, which is called dimensionality reduction convex hull method (DRCH).Through having 3d point set map to 2d plane, most initial 3D points in the convex hull are removed. Then, the remaining points are to generate 3D convex hull using any convex hull algorithm. The experiment demonstrates 3D DRCH is faster than general 3D convex hull algorithms. Its time complexity is O(r log r), where r is the number of points not in the hull. And DRCH can be generalized to higher-dimensional problems.

We propose an algorithm to sample the area of the smallest convex hull containing $$n$$ n sample points uniformly distributed over unit square. To do it, we introduce a new coordinate system for the position of vertexes and re-write joint distribution of the number of vertexes and their locations in the new coordinate system. The proposed algorithm is much faster than existing procedure and has a computational complexity on the order of $$O(T)$$ O ( T ) , where $$T$$ T is the number of vertexes. Using the proposed algorithm, we numerically investigate the asymptotic behavior of functionals of the random convex hull. In addition, we apply it to finding pairs of stocks where the returns are dependent on each other on the New York Stock Exchange.

The farthest line-segment Voronoi diagram illustrates properties surprisingly different from its counterpart for points: Voronoi regions may be disconnected and they are not characterized by convex-hull properties. In this paper we introduce the farthest hull and its Gaussian map as a closed polygonal curve that characterizes the regions of the farthest line-segment Voronoi diagram, and derive tighter bounds on the (linear) size of this diagram. With the purpose of unifying construction algorithms for farthest-point and farthest line-segment Voronoi diagrams, we adapt standard techniques to construct a convex hull and compute the farthest hull in O(n log n) or output sensitive O(n log h) time, where n is the number of line-segments and h is the number of faces in the corresponding farthest Voronoi diagram. As a result, the farthest line-segment Voronoi diagram can be constructed in output sensitive O(n log h) time. Our algorithms are given in the Euclidean plane but they hold also in the general Lp metric, 1 ≤ p ≤ ∞.