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.