 Open Access
 Total Downloads : 584
 Authors : Md. Kazi Salimullah, Md. Khalilur Rahman, Md. Najrul Islam
 Paper ID : IJERTV2IS50160
 Volume & Issue : Volume 02, Issue 05 (May 2013)
 Published (First Online): 08052013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
A New Technique for Solving “Convex Hull” Problem
Md. Kazi Salimullap, Md. Khalilur Rahman*2 , Md. Najrul Islam3
1,3 Dept. of Computer Science and Engineering, Islamic University, Kushtia, Bangladesh.
2Dept. of Applied Physics, Electronics and Communication Engineering, Islamic University, Kushtia, Bangladesh. *
Abstract
This paper presents a new technique for solving convex hull problem. To solve this problem the following steps have been used: i) Sorting the input points in ascending order(according to xcoordinate or ycoordinate). ii) Finding the leftmost and rightmost points in each horizontal line(HL)(when points are sorted according to ycoordinate) or top and bottom points in each vertical line(VL) (when points are sorted according to xcoordinate) including these sorted points. iii) Vertex recognition. If no. of HL or VL is k then recognizing 2k no. of points, the desired convex hull will be found although it contains kn no. of points (while each line has n points).Existing methodology computes the convex hull using all the input points. But in the new technique only 2k (where k is the no. of HL or VL) is used.
Keywords: Graham Scan method, Jarviss March method, Divide and Conquer method, Incremental method, Prune Search method.
Introduction
Convex hull is a part of computational geometry. Convex hull of a set S of points is the smallest convex polygon P for which each point in S is either on the boundary of P or in its interior. The convex hull of S is denoted by CH(S). Convexity has a number of properties that make convex polygons easier to work with than arbitrary polygons. For example, every diagonal of a convex polygon is a chord, every vertex of convex polygon is convex (that means its interior angle is less than or equal to 180 degree). There are some methods have already generated for solving convex hull problem. Among these methods Graham Scan
method1,5, Jarviss March method1, Divide and Conquer method2,69, Incremental method3
and PruneSearch methods4 are remarkable. Graham scan solves the convex hull problem by maintaining a stack Q of candidate points. Each point of the input set S is pushed once onto the stack, and the points that are not vertices of CH(S) are eventually popped from the stack. When the algorithm terminates, stack Q contains exactly the vertices of CH(S) in counter clockwise order of their appearance on the boundary. So the complexity in this method is increased with the increase of points. Jarviss March computes the convex hull of a set S of points by a technique known as package wrapping (or gift wrapping).Jarviss March simulates wrapping a taut piece of paper around the set S. By taping the end of the paper to the lowest point in the set is started, that is, to the same point p0 with which Grahams scan is started. This point is a vertex of the convex hull. The paper is pulled to the right to make it taut, and then it is pulled higher until it touches a point. This point must also be a vertex of the convex hull. Keeping the paper taut, it is continued in this way around the set of vertices
until coming back to the original point p0.This method is asymptotically faster than Grahams scan. But its complexity is related with the number of points and no. of vertices. In Divide and Conquer method it divides total input points into two parts that means each part contains kn/2(while HL=k or VL=k and each line has n points).Then generate two convex hulls and by combining these two hulls generate the desired CH(S).Although the performance is good but its complexity is also depends on the no. input points. Prune and search method is similar to the worst case linear time algorithm. This method is asymptotically fastest. Its complexity depends on the no. of vertices and points. The complexity of Incremental method is also depends on no. of input points. So the complexity of all the method depends on mainly no. of input points or no. of vertices or both. But in the new method it depends on mainly number of lines.
Analysis of the method
This method is based on the following formulas:

Every vertices of the convex hull must be the starting or ending points (among input points) of any horizontal or vertical line.

For top and bottom horizontal line or leftmost and rightmost vertical line the starting and ending points are must be vertices of desired convex hull.

The highest number of vertices in one line (horizontal or vertical) is less than or equal to two.

If the number of line(horizontal or vertical) is k at which all the points are lie then the total number of vertices is less than or equal to 2k.
Methodology
Let a set S of n points. All these points are inserted into a smallest polygon such that the polygon is a convex polygon. To do so it is needed to sort the points in ascending order(according to xcoordinate or ycoordinate).

When the points are sorted according to yordinate then the leftmost point and rightmost point in each horizontal line are found out. If there is one point in any horizontal line then leftmost point is equal to rightmost point. Now two chains are created; one is left chain and another is right chain. If the no. of horizontal lines is k then each chain has k no. of points. Total no. of points 2k lie in two chains. Moreover it is said that vertices of the desired convex hull CH(S) exist among these two chains.
Let left chain, L = {L1, L2 , L3 ,………………………, Lk }
And Right chain, R= {R1, R2 , R3 ,………………………, Rk }
where both L and R are the subsets of S.
By analysis, it is found L1 , R1 , Rk
and
Lk the vertices of CH(S). Now it must be recognized
the vertices from the rest points of two chains. For right chain it needs to find angles
R0 Rr Ri (whereR0 L1andRr R1.ifR1 L1thenR0 R1(x 1, y) and Rr is the recent vertex
and i 2,3,…………., k) and find the largest angle also. If
R0 R1R5
is largest then
R5 is the
recent vertex. Next step, it is essential to find the angle R1R5Ri (where i 6,7,……….., k)
and
find the next vertex following the previous step. No need to find the angles for the points that
are below the recent vertex
R5 because the upper point of the chain Rk
is the vertex. So there
is no probability to be the next vertex for points that are below the recent vertex. If for two points largest angle is same then farthest point is the vertex. Proceeding in this way it should be found out the vertices until arrived at Rk . For left chain it also be applied the same method. But in this case it will be started from Lk . For left chain it needs to find angles
Lk 1Lk Lk i (whereLk 1 Rk ifLk Rk thenLk 1 Lk (x 1, y) and Lk is the recent vertex and
i 1,2,3,…………., (k 1)) . All the vertices will be recognized from the left chain until arrived
at L1 .
For example: n=31 input points. k=No. of horizontal lines=7 which is shown in Figure1 and Figure2.
Figure1: Two chains (when HL is consider) Figure2: Convex hull (when HL is consider) Here two chains: left chain, L={L1, L2 , L3 , L4 , L5 , L6 , L7}
And right chain, R={R1, R2 , R3 , R4 , R5 , R6 , R7}
In these two chains
L1, L7 , R1
and
R7 are the known vertices. Between
R1 and
R7 the other
vertices are R3 and R6. To recognize these two vertices it needs to find the no. of angles as:
For
7
7
R3 R0 R1Ri (whereR0 L1) 6
i2
7
Here R0 R1R3 is largest so R3
is vertex.
For
R6 R1R3 Ri 4. Here R1R3R6
i4
is largest so
R6 is the next vertex.
For sureness the next vertex
R7 =0, since
R6 is vertex.
So total no. of angles in right chain = 6+4=10.
Total no. of vertices in right chain
R 2 ( without R1 and R7).
Again between
L1 and
L7 the other vertices are
L3 and
L6 . To recognize these two vertices
it needs to find the no. of angles as:
For
6
6
L6 L8 L7 L7i (whereL8 L7 ) 6. where L8 L7 L6 is largest so
i1
L6 is vertex.
For
5
5
L3 L7 L6 Li 5.whereL7 L6 L3
i1
is largest so
L3 is vertex.
2
2
For sureness the next vertex, L1 L6 L3Li 2.
i 1
where
L6 L3L1
is largest angle so
L1 is the
next vertex.
Total no. of angles in left chain L= 6+5+2=13
Total no. of vertices in left chain L
2 (without
L1 and
L7 ).
The desired convex hull CH(S) =
R1R3R6 R7 L7 L6 L3L1.
Total no. of vertices in CH(S) = 4+2+2=8.
Total no. of angles to recognize 8 vertices is 13+10=23.

When the points are sorted according to xordinate then top and bottom point in each line are found out. In this case two chains (upper and lower) will be created. Where
Upper chain, R= {T1,T2,T3,.,Tk} Lower chain, L= {B1, B2, B3,, Bk} L and R are both subset of S.
Here T1 and Tk in R and B1 and Bk in L are vertices known by sorting. Other vertices are recognized from the points of the two chains applying the same method that used in previous case.
For example, n=34 input points which are shown in figure3 and figure4. No. of vertical lines=10.Here two chains,
Upper chain, R= {T1,T2,T3,.,T10} Lower chain, L={B1, B2, B3,, B10}
Figure3: Two chains(when VL is consider) Figure4: Convex hull(when HL is consider)
Among these two chains T1, T10, B1and B10 are vertices known by sorting. The other vertices are T2, T5, T8, T9, B2, B8 that are determined by applying the same method that used in previous case. So the convex hull CH(S)= T1T2T5T8T9T10B1B2B8B10.Total no. of angles need to recognize all the vertices are=28+19=47.
Results and Discussion
From the above procedure it is seen that there are two major phases in the new method. One is sorting chain and another is vertices recognition phase. Vertex recognition phase is similar to Jarviss March method. But there is a difference to recognize a vertex, it needs to find the angles with all the input point in Jarviss March method where in the new method it needs to find the angles with the points that exist upper from recent vertex in that chain. Comparison between Jarviss March method and the new method is shown in the following table.
No. of lines
Total no. of points
Input points
No. of vertices
Vertices of the CH(S)
No. of angles needed in Jarviss March method
No. of angles needed in the new method
2
8
(2,1),(5,1),(9,1),(12,1),
4
(2,1),(12,1),
32
0
(2,5), (2,5), (8,5), (10,5)
(2,5) ,(10,5)
3
10
(1,7), (4,7), (6,7), (10,7),
4
(5,1), (10,1),
40
4
(1,2),(5,2),(7,2),(5,1), (1,1),
(1,7), (10,7)
(10,1)
4
15
(6,3),(3,3),(0,3),(5,3), (2,5),
6
(6,3),(5,3),
90
8
(4,5), (10,5), (12,5), (15,5),
(15,5),(15,10),
(5,10) (7,10),(10,10),(15,10),
(1,12),(5,12)
(1,12), (5,12)
4
20
(6,3),(3,3),(0,3),(5,3),
8
(6,3), (10,3),
160
9
(10,3), (10,5), (4,5), (10,5),
(10,5),(15,5),
(12,5), (15,5)(10,10),(5,10),
(10,10),
(7,10),(10,10),(15,10)
(15,10),(2,12),
(2,12),(0,12),(1,12),(5,12),
(7,12)
(7,12)
5
15
(1,2),(4,2),(10,2),
7
(1,2),(10,2),
105
13
(5,6), (5,6), (12,6),
(5,6),(12,6),
(1,10), (3,10), (5,10),
(3,15),(6,18),
(3,15)(3,15),(4,15),
(13,18)
(6,18),(10,18), (13,18)
Table: Comparison between Jarviss March method and the new method.
There is a similarity with the new method and Jarviss March method so it is compared with Jarviss March method and the method in the Table. From the Table it is seen that the no. of angles for recognizing the vertices depends on the number of lines and position of vertices on the chain, in the new method it does not depend on the no. of points. But in Jarviss March method the no. of angles depends on both no. of vertices and the no. of points. From the above Table it is noticed that the performance of the new method is very high than J. March method.
Conclusion
This new method is a successful technique for solving convex hull problem. But there are some problems. In vertex recognition phase, when more than one angle is the largest then it is difficult to find out the farthest point. Moreover to find out the largest angle is also a problem. If it is considered the use orientation parameter for vertices recognition then its efficiency will be increased.
References

Thomas H. Cormen, Charles E. Leiserson, Ronald L.Rivest, Clifford Stein; Introduction to Algorithms, (The MIT Press, McGrawHill Book Company, Second edition), pp. 947961.

Michael J. Laszlo. Computational Geometry and Computer graphics in C++, (Prentice Hall of India private Ltd, Eastern Economy Edition), pp.203208

Michael J. Laszlo; aforesaid, pp.139145

Thomas H. Cormen et al; aforesaid, pp.189192

Ellis Horowitz, Sartaj Sahni and S.Rajasekaran; Fundamentals of Computer Algorithms,(Galgotia Publications pvt. Ltd. New Delhi,2008),pp.187189

Ellis Horowitz et al; aforesaid; pp.188191

F. Preparata and M.I.Shamos; Computational Geometry; (SpringerVerlag, 1985)

K. Mulmuley; Computational Geometry: An Introduction Through Randomized Algorithms;(ParenticeHall, New Delhi, 1994)

U Manber; Introduction to Algorithms: A Creative Approach;(AddisonWesley, New Delhi,1989)
