A New Technique for Solving “Convex Hull” Problem

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 x-coordinate or y-coordinate). ii) Finding the leftmost and rightmost points in each horizontal line(HL)(when points are sorted according to y-coordinate) or top and bottom points in each vertical line(VL) (when points are sorted according to x-coordinate) 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,6-9, Incremental method3

and Prune-Search 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:

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

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

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

4. 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 x-coordinate or y-coordinate).

1. When the points are sorted according to y-ordinate 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.

   Figure-1: Two chains (when HL is consider) Figure-2: 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.

2. When the points are sorted according to x-ordinate 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 figure-3 and figure-4. No. of vertical lines=10.Here two chains,

   Upper chain, R= {T1,T2,T3,.,T10} Lower chain, L={B1, B2, B3,, B10}

   Figure-3: Two chains(when VL is consider) Figure-4: 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

   1. Thomas H. Cormen, Charles E. Leiserson, Ronald L.Rivest, Clifford Stein; Introduction to Algorithms, (The MIT Press, McGraw-Hill Book Company, Second edition), pp. 947-961.

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

   3. Michael J. Laszlo; aforesaid, pp.139-145

   4. Thomas H. Cormen et al; aforesaid, pp.189-192

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

   6. Ellis Horowitz et al; aforesaid; pp.188-191

   7. F. Preparata and M.I.Shamos; Computational Geometry; (Springer-Verlag, 1985)

   8. K. Mulmuley; Computational Geometry: An Introduction Through Randomized Algorithms;(Parentice-Hall, New Delhi, 1994)

   9. U Manber; Introduction to Algorithms: A Creative Approach;(Addison-Wesley, New Delhi,1989)