1. Introduction
The construction of planar convex hull is one of the most fundamental problems in computational geometry. The applications of convex hull spread over large number of fields including pattern recognition, regression, collision detection, area estimation, spectrometry, topology, etc. For instance, computer animation, the most crucial section of computer gaming, requires fast approximation for real-time response. Consequently, it is evidential from literature that numerous studies focus on fast approximation of different geometric structures in computer graphics [1,2]. Moreover, the construction of exact and approximate convex hull is used as a preprocessing or intermediate step to solve many problems in computer graphics [3,4].
Convex hull for a given finite set 
of 
points where 
denotes the 
-dimensional Euclidean space, is defined as the smallest convex set that contains all the 
points. A set 
is convex if for two arbitrary points
, the line segment 
is entirely contained in the set
. Alternatively, the convex hull can be defined as the intersection of all halfspaces (or half-planes in
) containing
. The main focus of this article is limited on the convex hull in Euclidean plane
.
2. Previous Work
Because of the importance of convex hull, it is natural to study for improvement of running time and storage requirements of the convex hull algorithms in different Euclidean spaces. Graham [5] published one of the fundamental algorithms of convex hull, widely known as Graham’s scan as early as 1972. This is one of the earliest convex hull algorithms with 
worst-case running time. Graham’s algorithm is asymptotically optimal since 
is the lower bound of planar convex hull problem. It can be shown [6] that 
is a lower bound of a similar but weaker problem of determining the points belonging to the convex hull, not necessarily producing them in cyclic order.
However, all of these lower bound arguments assume that the number of hull vertices 
is at least a fraction of
. Another algorithm due to Jarvis [7] surpasses the Graham’s scan algorithm if the number of hull vertices 
is substantially smaller than
. This algorithm with 
running time is known as Jarvis’s march. There is a strong relation between sorting algorithm and convex hull algorithm in the plane. Several divide-and-conquer algorithms including MergeHull and QuickHull algorithms of convex hull modeled after the sorting algorithms [8] and the first algorithm Graham’s [5] scan uses explicit sorting of points.
In 1986, Kirkpatrick and Seidel [9] proposed an algorithm that computes the convex hull of a set of 
points in the plane in 
time. Their algorithm is both output sensitive and worst case optimal. Later, a simplification of this algorithm [9] was obtained by Chan [10]. In the following year Melkman [11] presented a simple and elegant algorithm to construct the convex hull for simple polyline. This is one of the on-line algorithms which construct the convex hull in linear time.
Approximation algorithms for convex hull are useful for applications including area estimation of complex shapes that require rapid solutions, even at the expense of accuracy of constructed convex hull. Based on approximation output, these algorithms of convex hull could be divided into three groups—near, inner, and outer approximation algorithms. Near, inner, and outer approximation algorithms compute near, inner, and outer approximation of the exact convex hull for some point set respectively.
In 1982, Bentley et al. [12] published an approximation algorithm for convex hull construction with 
running time. Another algorithm due to Soisalon-Soininen [13] which uses a modified approximation scheme of [12] and has the same running time and error bound. Both of the algorithms are the inner approximation of convex hull algorithm. The proposed algorithm in this article is a near approximation algorithm of 
running time.
3. Approximation Algorithm
Let 
be the finite set of 
points in general position and the (accurate) convex hull of 
be
. Kavan, Kolingerova, and Zara [14] proposed an algorithm with 
running time which partitions the plane 
into 
sectors centered in the origin. Their algorithm requires the origin to be inside the convex hull. (It is possible to choose a point 
and translate all the other points of 
accordingly using additional steps in their algorithm). Conversely, we partition the plane 
into 
vertical sector pair with equal central angle 
in the origin and for our algorithm the origin 
could be located outside of the convex hull. The sets represent the vertically opposite sectors that form the vertical sector pairs defined as
where, 
and the central angle
. Then, the sets 
and 
denote the points belonging to the set 
in sectors 
and 
respectively. Formally,
A pair of unit vectors 
and 
obtain in 
th vertical sector pair as
The maximum projection magnitudes in the directions of 
and 
are (Figure 1)
The definition of max function is extend to return 
for no parameter. The sets of points which provide the maximum projection magnitude in the sectors of 
th vertical sector pair are
The vectors that produce the maximum magnitude in the directions of 
and 
for some points in the 
th vertical sector pair are
The magnitude of the vectors 
and 
could be 
for the 
th vertical sector pair containing less than two points. The sets 
and 
containing all the finite vectors in the ranges 
and
, are
Let, 
and 
contains at least three terminal points of the vectors in general position to construct the convex hull.
Figure 1. An example of convex hull CH16 constructed using proposed algorithm based on a set of 50 points.
The convex hull approximation of 
vertical sector pairs according to the proposed algorithm in this article is:
4. Implementation
The input of the algorithm 
is a set of 
points in general position. For simplicity, we assume that the origin 
and
. (This assumption can be achieved by taking a point arbitrarily close to the origin instead of the origin itself, within the upper bound of error calculated in Section 5) (Figure 2).
We also assume that at least two vertical sector pairs together contains minimum three points (where none of these two are empty). The assumption can be reduced to one of the requirements of minimum three points input (i.e.,
) of convex hull. To illustrate that, let us consider 
and 
to be two points in 
such that 
where 
is the origin. Such two points do exist if no three points are collinear in 
(i.e., the points of 
are in general position). If 
is the bisector of
, then adding the angle of 
from positive 
-axis as an offset to every vertical sector pair ensures that all the input points cannot be in the same vertical sector pair. Thus, the assumption is satisfied. Alternatively, if less than three absolute values in 
are finite, then for each
, assign 
to 
and 
where these are infinite. (The next pa-
ragraph contains details about M.) Therefore, the number of points in 
must be at least three.
A circular array 
is used to contain the 
pairs of unit vectors of all the 
vertical sector pairs and another circular array 
is used to hold the number of 
pairs of maximum projection magnitude in all the 
vertical sector pairs. Both circular arrays have the same size of 
and use zero based indexing scheme. The function atan2 is a variation of function arctan with point as a parameter. The function returns the angle in radians between the point and the positive 
-axis of the plane in the range of
. The function anglex searches sequentially for the index of maximum angular distance between two consecutive positive finite vectors (computed using projection magnitude with index referring angle). If the index is 
such that maximum angle occurs in between 
and
, the anglex function returns
. The final convex hull is constructed using Melkman’s [11] algorithm from set of 
points which are the terminal points of finite vectors computed in steps 14 and 15. If the first three points of 
are collinear, displacing one of these points within the error bound solves the problem.
Since the vertices of the convex hull produced by the proposed algorithm are not necessarily in the input point set
, the algorithm cannot be applied straight away to solve some other problems. Let us consider another circular array 
of 
size which used to contain the points generating the inner products of
. Adding the point 
instead of 
to the sequence 
in Steps 14 and 15 ensures that the vertices of the convex hull will be the points from
. These modifications of the algorithm allow us to solve some problems including approximate farthest-pair problem but increase the upper bound of error (described in Section 5) to
.
5. Error Analysis
There are different schemes for measuring the error of an approximation of the convex hull. We measured the error as distance from point set of accurate convex hull
. The distance of an arbitrary point 
from a set 
is defined as
Formally the approximation error 
can be defined as
It is sufficient to determine the upper bound of error 
of the approximate convex hull
. Let, 
be be a point lying outside of the convex hull 
and 
be the origin. Suppose that, 
is an edge of the approximate convex hull (as shown in Figure 3).
Therefore, the distance of the point 
from the
is
.
The distance of the point 
from vertex 
is
. Thus,
.
Let, 
and
. Thus we obtain
It follows that the minimum distance 
directly depends on 
which is denoted as function
. Thus, the upper bound of approximation error 
is
. If 
approaches to infinity, the 
converges to
.
For instance, when k approaches to a large value, the area approximation error of the circle is reducing exponentially as shown in Figure 4. Therefore, this algorithm is more optimize than the KKZ algorithm [14] with respect to error bound as shown in Figure 5.
6. Correctness
Theorem 1. The approximation algorithm produces the convex hull from a set of points in 
correctly within the prescribed error bound.
Proof. Since, Melkman’s algorithm can construct the convex hull correctly for points on a simple polygonal chain, it suffices to prove that the sequence of points 
denotes a simple polygonal chain. (Melkman [11] published the on-line algorithm of convex hull with formal proof of correctness in 1987).
Suppose that, the plane 
is partitioned into 
vertical sector pairs which correspond to the sequence
of 
simple sectors. The sequence
of sectors is ordered according to the angle measured anticlockwise. If 
is a half-line (denoting the set of points on the half-line) from the origin in the direction of the unit vector of the sector
, then the sequence
represents all the half-lines correlated with the sequence
. According to the algorithm all the points of 
must be distinct (as referred in steps 9-10) and lying on some of the half-lines of
. The sequence of half-lines 
where each contained at least one point from
, is
Each half-line 
can contain at most two points of
. Let, 
are points on each halfline 
such that
. If a half-line 
contains only one point of
, the length of virtual 
is zero with 
and 
refer to the same point of 
(e.g., 
contains only one point in the Figure 6). Let 
denotes the angle from 
to 
where 
and 
are half-lines from the origin. Since the angle between two consecutive half-lines 
and 
(because 
for our assumptions 
and 
in the algorithm), no two line segments 
and 
intersect each other, for all
. However, the line segment 
could cross the polygonal chain 
if the angle
. The equation of 
(derived using the law of sines and basic properties of triangle) also illustrates this fact mathematically for 
(as shown in the Figure 6).
The solution with minimum magnitude of the above equation is negative for
, even if
. Thus the line segment 
could intersect with the edges of the polygonal chain only if
. If the maximum angle between two consecutive half-lines is 
for some
, then anglex function returns the index 
that ensures the construction a simple polygonal chain 
where 
and all the indices are modulo
. Thus the sequence of points 
represents a simple polygonal chain. (It is possible to prove the algorithm obtained by interchanging the steps 14 and 15, using a similar method). 
Theorem 2. If 
is the number of input points and 
is the number of vertical sector pairs in
, then the running time of the proposed algorithm is
.
Proof. Let us estimate the running time for each part of the algorithm to prove that the algorithm compute the approximate convex hull in 
time. It is clear that, the initialization steps 2-5 take 
time. Since, the next loop of steps 6-10 iterates for each point
, thus it takes 
time considering constant time for floor function. According to the description of anglex function in Section 4, the function can be implemented in 
time because it requires 
iterations to compute the index. The loop of steps 13-15 takes 
time and Melkman’s [11] algorithm runs in linear time. Steps 1 and 11 require constant time. Thus the running time of the algorithm is
.
7. Conclusion
Geometric algorithms are frequently formulated under the non-degeneracy assumption or general position assumption [15] and the proposed algorithm in this article is also not an exception. To make the implementation of the algorithm robust an integrated treatment for the special cases can be applied. There are other general techniques called perturbation schemes [16,17] to transform the input into general position and allow the algorithm to solve the problem on perturbed input. Both symbolic perturbation and numerical (approximation) perturbation (where perturbation error is consistent with the error bound of the algorithm) can be used on the points of 
to eliminate degenerate cases.
8. Acknowledgements
This research is supported by a grant from Independent University Bangladesh (IUB).
Appendix
The article describes a near approximation algorithm for convex hull however it is possible to extend the concept for inner as well as outer approximation algorithms for convex hull. An illustration of inner approximate convex hull algorithm is shown in Figure 7.