Search

In this paper, we present an efficient improvement of gift wrapping algorithm for determining the convex hull of a finite set of points in $\mathbb {R}^{n}$ space, applying the best restricted area technique inspired from the Method of Orienting Curves (this method was used successfully in computational geometry by An and Trang in Numerical Algorithms 59, 347–357 (2012), Optimization 62, 975–988 (2013)). The numerical experiments on the sets of random points in two- and three-dimensional space show that the running time of our algorithm is faster than the gift wrapping algorithm and the newest modified 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.

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<

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

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.

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.

An important problem in distance geometry is of determining the position of an unknown point in a given convex set such that its longest distance to a set of finite number of points is shortest. In this paper we present an algorithm based on subgradient method and convex hull computation for solving this problem. A recent improvement of Quickhull algorithm for computing the convex hull of a finite set of planar points is applied to fasten up the computations in our numerical experiments.

Data imprecision constitutes an important gap between theory and practice in computational geometry. A lot of research about imprecision in computational geometry is directed at computing the convex hull of imprecise points rather than imprecise line segment intersection. In this paper we introduce an algorithm to construct the convex hull for a set of imprecise line segment intersection in time.

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.

This paper presents a novel tracking algorithm based on the convex hull representation model with sparse representation. The tracked object is assumed to be within the object convex hull and the candidate convex hull in the meanwhile. The object convex hull consists of a principle component analysis (PCA) subspace, and the candidate convex hull is constructed by all candidate samples with the sparsity constraint. Then we propose the objective function for our convex hull representation model, and design an iterative algorithm to solve it effectively. Finally, we present a tracking framework based on the proposed convex hull model and a simple online update scheme. Both qualitative and quantitative evaluations on some challenging video clips show that our tracker achieves better performance than other state-of-theart methods.

Computational geometry is the mathematical science of computation by using the algorithm analysis to solve the problems of geometry. The problems of computational include polygon triangulations, convex hulls, Voronoi diagrams, and motion planning. Convex hull is the set of points that form a convex polygon that covers the entire set of points. The algorithms for determining the convex hull, among others, Graham Scan, Jarvis March, and Divide and Conquer. In the two-dimensional case, Graham Scan algorithm is highly efficient in the use of time complexity. This article discusses the quest convex hull of the data bank debtors, some of the data used to look at the classification accuracy of the convex hull formed. The coordinates of all the data found by using principal component analysis.After the data are analyzed, we get the accuracy of classification by 74%.

In this paper ,a new algorithm is proposed for improving speed of calculating convex hull of planar point set .The algorithm creates a square mesh to manage points ,when eliminating points which are obviously in convex hull ,selecting or eliminating of points can be converted to that of grid , work of calculation depends on points near edges of convex hull and density of grid but not the number of points ;at the meantime ,remainder points are sorted roughly .When calculating convex hull of remainder points ,a method is presented which can take advantage of order of remainder points ,it calculates boundaries of convex hull segment by segment ,then ,combines the boundaries to form convex hull.

In this paper, we suggest an improved Convex Hull algorithm considering sort in plane point set. This algorithm has low computational complexity since processing data are reduced by characteristic of extreme points. Also it obtains a complete convex set with just one processing using an convex vertex discrimination criterion. Initially it requires sorting of point set. However we can`t quickly sort because of its heavy operations. This problem was solved by replacing value and index. We measure the execution time of algorithms by generating a random set of points. The results of the experiment show that it is about 2 times faster than the existing algorithm.

The convex hull is one of main research problems in computational geometry, it has been wildly used in computer graphics, pattern recognition, image processing, GIS and military, etc. In this paper, a simple and fast algorithm for the convex hull of planer point set is proposed by deleting those “useless” points. In case of points distributed randomly in the planer area, our algorithm is more efficient than the classical Graham Scan Algorithm in terms of processing.

A combinatorial algorithm to compute the orthogonal hull of a digital object imposed on a background grid is presented in this paper. The resolution and complexity of the orthogonal hull can be controlled by varying the grid size, which may be used for a multiresolution analysis of a given object. Existing algorithms on finding the convex hull are based on divide and conquer strategy, sweepline approach, etc., whereas the proposed algorithm is combinatorial in nature whose time complexity is linear on the object perimeter instead of the object area. For a larger grid size, the perimeter of an object decreases in length in terms of grid units, and hence the runtime of the algorithm reduces significantly. The algorithm uses only comparison and addition in the integer domain, thereby making it amenable to usage in real-world applications where speed is a prime factor. Experimental results including the CPU time demonstrate the elegance and efficacy of the proposed algorithm.

A convex hull of points in E2 is used in many applications. In spite of low computational complexity O(h logn) it takes considerable time if large data processing is needed. We present a new algorithm to speed up any planar convex hull calculation. It is based on a polar space subdivision and speed up known convex hull algorithms of 3,7 times and more. The algorithm estimates the central point using 10% of the data, this point is taken as the origin for the polar subdivision. The space subdivision enables a fast and very efficient reduction of the given points, which cannot contribute to the final convex hull. The proposed algorithm iteratively approximates the convex hull, leaving only a small number of points for the final processing, which is performed using a "standard" algorithm. Non-eliminated points are then processed by a selected standard convex hull algorithm. The algorithm is simple and easy to implement. Experiments proved numerical robustness as well.

Objectives: This article presents a hybrid convex hull algorithm to reduce computational resources in fingertips detection from an image. Methodology: In this paper, we suggest to reduce the computational resources by leveraging on two proven algorithms and techniques in order to extract the convex hull vertices directly from a binary image without going through the edge detection process. This is done by embedding Bresenham algorithm within Jarvis March to replace most of the work required in the edge detection process. Findings: The hybrid convex hull algorithm which we have suggested requires only four global extreme points to begin with and thus the pre-processing step takes much less resources. The new algorithm yields time complexity of O(N 2 ). Novelty/Improvement: The hybrid convex hull algorithm offers a direct way to detect the convex hull of the original image without edge detection process.

In order to accelerate computing the convex hull on a set of n points, a heuristic procedure is often applied to reduce the number of points to a set of s points, s ? n, which also contains the same hull. We present an algorithm to precondition 2D data with integer coordinates bounded by a box of size p × q before building a 2D convex hull, with three distinct advantages. First, we prove that under the condition min(p, q) ? n the algorithm executes in time within O(n); second, no explicit sorting of data is required; and third, the reduced set of s points forms a simple polygonal chain and thus can be directly pipelined into an O(n) time convex hull algorithm. This paper empirically evaluates and quantifies the speed up gained by preconditioning a set of points by a method based on the proposed algorithm before using common convex hull algorithms to build the final hull. A speedup factor of at least four is consistently found from experiments on various datasets when the condition min(p, q) ? n holds; the smaller the ratio min(p, q)/n is in the dataset, the greater the speedup factor achieved.

Computing the convex hull of a point set is requirement in the GIS applications. This paper studies on the problem of minimum convex hull and presents an improved algorithm for the minimum convex hull of planar scattered point set. It adopts approach that dividing the point set into several sub regions to get an initial convex hull boundary firstly. Then the points on the boundary, which cannot be vertices of the minimum convex hull, are removed one by one. Finally the concave points on the boundary, which cannot be vertices of the minimum convex hull, are withdrew. Experimental analysis shows the efficiency of the algorithm compared with other methods.

This paper presents a fast convex hull algorithm for a large point set. The algorithm imitates the procedure of human visual attention derived in a psychological experiment. The merit of human visual attention is to neglect most inner points directly. The proposed algorithm achieves a significant saving in time and space in comparison with the two best convex hull algorithms mentioned in a latest review proposed by Chadnov and Skvortsov in 2004. Furthermore, we propose to use an affine transformation to solve the narrow shape problem for computing the convex hull faster.

This article describes an efficient convex hull algorithm for finite point sets in 3D based on the idea of the Method of Orienting Curves (introduced by Phu in Optimization, 18 (1987) pp. 65–81, for solving optimal control problems with state constraints). The actual run times of our algorithm and known gift-wrapping algorithm on the set of random points (in uniform distribution) show that our algorithm runs significantly faster than the gift-wrapping one.

The maxima-finding is a fundamental problem in computational geometry with many applications. In this paper, a volume first maxima-finding algorithm is proposed. It is proved that the expected running time of the algorithm is N+o(N) when choosing points from CI distribution, which is a new theoretical result when the points belong to d(>2) dimensional space. Experimental results and theoretical analysis indicate that the algorithm runs faster than the Move-To-Front maxima-finding algorithm.

This paper introduced points and directed line segment relation judgment method, the characteristics of generation and Graham method using the original convex hull generation algorithm of convex hull discrete points of the convex hull, an improved algorithm for planar discrete point set is proposed. The main idea is to use quadrilateral to divide planar discrete point set into five blocks, and then by judgment in addition to the four district quadrilateral internally within the point is in a convex edge. The result shows that the method is relatively simple program, high computational efficiency.

Given a dataset of two-dimensional points in the plane with integer coordinates, the method proposed reduces a set of n points down to a set of s points s ≤ n, such that the convex hull on the set of s points is the same as the convex hull of the original set of n points. The method is O(n). It helps any convex hull algorithm run faster. The empirical analysis of a practical case shows a percentage reduction in points of over 98%, that is reflected as a faster computation with a speedup factor of at least 4.

In this article, we present an efficient algorithm to determine the convex hull of a finite planar set using the idea of the Method of Orienting Curves (introduced by Phu in Zur Losung einer regula...

Finding the convex hull of n points in the plane requires O ( n log n ) time in general. In Devroye and Toussaint [1993] and Golin et al. [2002] the problem of computing the convex hull of the intersection points of n lines was considered, where the lines are chosen randomly according to two various models. In both models, linear-time algorithms were developed. Here we improve the results of Devroye and Toussaint [1993] by giving a universal algorithm for a wider range of distributions.

In this paper, based on combined homotopy interior point method we propose an interior point algorithm for convex nonlinear programming. The algorithm ensures that the obtained iterative points are interior points of the feasible set in terms of the technique of β-cone neighborhood. We establish the global convergence of the algorithm. Furthermore, it is shown that the algorithm has O ( n L ) iteration complexity. The preliminary numerical experiments indicate that the algorithm is efficient.

Convex hull is one of the important part of computational geometry. Many applications have used this method as part of their system. In this research, the novel Q-scanning of convex hull algorithm is proposed. The algorithm reduces computational complexity of conventional convex hull algorithm. The initial step of the proposed method is dividing the problem of convex hull into four subset hull. Each hull has its extreme point. In the process, the extreme point will move until meet convergence. The proof of the concept is conducted in Matlab software. The method of the experimental setup is a convex construction hull from some finite points of natural number which set randomly. The experiment shows that the algorithm is able to build a convex hull with O(n) of computational complexity and can be used as alternative approach for convex hull problem.

Graham scan, a computational geometric algorithm for finding a two-dimensional convex hull, is introduced to calculate binary phase diagrams. This algorithm is modified and applied to find the convex hull of discrete points in the space of Gibbs energy vs mol fraction. The modified Graham scan algorithm has a very low computational cost, which improves efficiency in binary phase diagram calculation.

The S-K algorithm (Schlesinger-Kozinec algorithm) and the modified kernel technique due to Friess et al. have been recently combined to solve SVM with L-2 cost function. In this paper, we generalize S-K algorithm to be applied for soft convex hulls. As a result, our algorithm can solve v-SVM based on L-1 cost function. Simple in nature, our soft algorithm is essentially a algorithm for finding the epsilon-optimal nearest points between two soft convex hulls. As only the vertexes of the hard convex hulls are used, the obvious superiority of our algorithm is that it has almost the same computational cost as that of the hard S-K algorithm. The theoretical analysis and some experiments demonstrate the performance of our algorithm. (C) 2004 Elsevier B.V. All rights reserved.

A space-efficient algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. We describe four space-efficient algorithms for computing the convex hull of a planar point set.

An algorithm for constructing the convex hull of a finite set of points in a d-dimensional space for a minimum number of iterations is proposed.

In this paper, we propose a parallel algorithm to solve the convex hull problem for an (n×n) multi-leveled image using a reconfigurable mesh connected computer of the same size as a computational model. The algorithm determines parallely the convex hull of all the connected components of the multileveled image. It is based on some geometric properties and a top-down strategy. The complexity of the algorithm is O(log n) times. Using some approximations on the component contours, this complexity is reduced to O(log m) times where m is the number of the vertices of the convex hull of the biggest component of the image.This complexity is reached thanks to the polymorphic properties of the mesh where all the components are simultaneously and separately processed.

Shapes extraction methods for getting two or more characters in convex hull or approximate convex hull are proposed in this paper. Proposed approaches use Genetic Algorithm (GA) with a improved local search or new local search method, which can get some characters as a shrink-wrapping from convex hull or approximate convex hull. The test problems are newly provided, which are made of the original problems in previous study. After obtaining convex hull or approximate convex hull, a local search method is applied to get the shape of objects in the hull. The experimental results show that proposed local search methods get the shape of objects with success.

Convex hull vertices extraction from a binary image to detect fingertips always involves multi-step pre-processing algorithm such as edge detection algorithms, before the actual convex hull algorithm can be applied on the image. The pre-processing steps often take up much computational resources. In this paper, we endeavour to reduce the computational resources by introducing a hybrid convex hull algorithm, which is able to extract the convex hull vertices directly from a binary image without going through the edge detection process. Bresenham algorithm is embedded within Jarvis March to replace most of the work required in the edge detection process. In this respect, our pre-processing step is simple and detect only four global extreme points' extraction. The new algorithm yields time complexity of O(N2).

A fast SVM learning algorithm is proposed according to incremental learning and center convex hull operator. It is established on analyzing the relevance of support vector and convex hull from the angle of calculation geometry. The convex hull of current training samples is solved in the first place. Further, Euclidean distance elimination is applied to convex hull. Meanwhile, every time when the incremental learning is going on, the training samples should contain samples violated KKT condition in previous sample set, experiment results indicate that the algorithm effectively shortens training time while classification accuracy keep a satisfied level.

In this paper we address the problem of computing a minimal representation of the convex hull of the union of k H-polytopes in Rd. Our method applies the reverse search algorithm to a shelling ordering of the facets of the convex hull. Efficient wrapping is done by projecting the polytopes onto the two-dimensional space and solving a linear program. The resulting algorithm is polynomial in the sizes of input and output under the general position assumption.

We present an algorithm for computing the convex hull of a finite set of points. The algorithm is based on a version of Graham scan with the following additional features: • If the points are already (single precision) machine numbers, the computation is rounding-error free, that is, the computed hull is the hull that would have been computed if real arithmetic was available. • If the points are arbitrary numbers, the algorithm renders the smallest possible machine representable convex hull that includes the exact convex hull. • The computation time is still O(n log 2n). • Only floating point arithmetic with double mantissa length is required. No mantissa splitting or other mantissa manipulations are needed; one only has to know the exponent parts of the numbers. Also, no fixed point accumulator is needed. • Single precision interval arithmetic is recommended for accelerating the computation, but is not necessary. • All of these aims are achieved with a new method for exact determination of the sign of a sum.

This paper presents a new fast algorithm to compute the twodimensional inclusion test of a point in the convex hull of a set of points, without computing the convex hull. The algorithm is based on the classification of the points in octants of the plane. This classification step for each point requires only simple test operations, and makes the algorithm run in at worst, O(ns). For point sets larger than 11 points, the proposed algorithm is faster than other known approaches. The paper includes a practical evaluation of the algorithm, comparing it with several previously known approaches.

We present a randomized algorithm for computing portions of an arrangement of n arcs in the plane, each pair of which intersect in at most t points. We use this algorithm to perform online walks inside such an arrangement (i.e., compute all the faces that a curve, given in an online manner, crosses) and to compute a level in an arrangement, both in an output-sensitive manner. The expected running time of the algorithm is $O(\lambda_{t+2}(m+n)\log n)$, where m is the number of intersections between the walk and the given arcs. No similarly efficient algorithm is known for the general case of arcs. For the case of lines and for certain restricted cases involving line segments, our algorithm improves the best known algorithm of [M. H. Overmars and J. van Leeuwen, J. Comput. System Sci., 23 (1981), pp. 166--204] by almost a logarithmic factor.

Many heuristic algorithms for solving geometric traveller problems utilize the extreme points of the convex hull of the given points to provide an initial partial tour. These heuristics are supported by the property that an optimal lour visits the extreme points of the convex hull in the order that they appear on the hull boundary. We show that when all the given points in the problem are assigned to a set of nested hulls, a similar property usually holds for each of these hulls. An algorithm which exploits this nested hull technique significantly improves upon computational efficiency without sacrificing solution quality as compared with other convex hull heuristics. Computational results are given.

To find a convex hull for n points in d-dimensional space, the optimal algorithm has time complexity O(n^[^d^2^]). When n and d are large, the execution time is very long. In this paper, we propose an approximate algorithm for computing multidimensional convex hulls. This algorithm finds quasi-two-side approximation to the hull to reduce the time for computing the exact hull boundary. To yield an @e-approximate convex hull, it has time complexity O(@e^-^1^(^d^-^1^)n) and storage complexity O(@e^-^1^(^d^-^1^)). The approximate algorithm has several advantages: (1) it can easily be implemented, (2) it is suitable for parallel implementation, (3) it is much faster than the exact algorithm, (4) the user can choose to get more accurate results using longer computation time, and (5) it can be applied to solve many problems related to convex hull computation.

We present an algorithm for identifying the extreme rays of the conical hull of a finite set of vectors whose generated cone is pointed. This problem appears in diverse areas including stochastic programming, computational geometry, and non-parametric efficiency measurement. The standard approach consists of solving a linear program for every element of the set of vectors. The new algorithm differs in that it solves fewer and substantially smaller LPs. Extensive computational testing validates the algorithm and demonstrates that for a wide range of problems it is computationally superior to the standard approach.

A set of planar objects is said to be of type m if the convex hull of any two objects has its size bounded by 2m. In this paper, we present an algorithm based on the marriage-before-conquest paradigm to compute the convex hull of a set of n planar convex objects of fixed type m. The algorithm is output-sensitive, i.e. its time complexity depends on the size h of the computed convex hull. The main ingredient of this algorithm is a linear method to find a bridge, i.e. a facet of the convex hull intersected by a given line. We obtain an O(nβ(h,m log h)-time convex hull algorithm for planar objects. Here β(h,2)=O(1) and β(h,m) is an extremely slowly growing function. As a direct consequence, we can compute in optimal Θ(n log h) time the convex hull of disks, convex homothets, non-overlapping objects. The method described in this paper also applies to compute lower envelopes of functions. In particular, we obtain an optimal Θ(n log h)-time algorithm to compute the upper envelope of line segments.

The divide-and-conquer algorithm for constructing three-dimensional convex hulls is implemented in a numerically robust manner. The approach taken here is a topology-oriented approach, in which the topological consistency is considered more important than the result of numerical computation. This is the first implementation of the divide-and-conquer algorithm for the three-dimensional convex hull using the topology-oriented approach. Implementation details are described together with computational experiments.