Online maintenance of the convex hull in the plane

Abstract

The convex hull of a set of points in the plane is defined as the point, the shortest line segment, or the minimum area convex polygon containing all the points in the set. There are mainly two types of the convex hull problem: offline and online. Suppose that points arrive one by one, and the position of the next point is always unpredictable. Then the maintenance of the convex hull of the currently available set of points is called the online convex hull problem. If all the points are available from the beginning, then the construction of the convex hull is called the offline convex hull problem. The offline convex hull problem has been extensively studied in literature and several optimal algorithms are available for this. However, there are only two algorithms available in literature to solve the online convex hull problem. Furthermore, these two algorithms are theoretical ones without corresponding computer implementations. Therefore, an optimal offline algorithm is used in practice to solve the online convex hull problem. This approach takes O (k log k) update time and O (n2log n) total time. A new practical online convex hull algorithm is proposed in this work. The convex hull is represented using the list of edges in arbitrary order. The existing convex hull should be modified only if the new point arrives outside. The edges visible to the new point are deleted from the list. Consequently, the convex hull becomes incomplete. Then, at most two edges are added to the list in order to complete the convex hull. Thus, the convex hull is maintained online. The algorithm can be implemented using an object-oriented programming language. The proposed algorithm takes O (k) update time and O (n2) total time. Therefore, the proposed algorithm is faster than the existing practical approach.