Start Submission Become a Reviewer

Reading: An efficient planar incremental convex hull algorithm to find the edges of the boundary poly...

Download

A- A+
Alt. Display

Research Articles

An efficient planar incremental convex hull algorithm to find the edges of the boundary polygon of the convex hull of a set of points

Authors:

K. R. Wijeweera ,

University of Peradeniya, Peradeniya, LK
About K. R.

Postgraduate Institute of Science

 

Department of Computer Science, Faculty of Science, University of Ruhuna, Matara

X close

S. R. Kodituwakku

University of Peradeniya, Peradeniya, LK
About S. R.

Postgraduate Institute of Science

 

Department of Statistics and Computer Science, Faculty of Science, University of Peradeniya, Peradeniya

X close

Abstract

The definition of the convex hull of a set of points is the smallest convex set containing all the points. Many algorithms have been proposed with the worst case time complexity is equal to O (n log n). It has been proved that the lower bound of time complexity for construction of the convex hull is O (n log n). However, these algorithms are static and require all points at the start. Suppose that points reach sequentially one after one and the convex hull needs to be maintained at each insertion of a point. The convex hull should be constructed from the scratch to handle each point insertion if a static convex hull algorithm was used. This process consumes O (n log n) time and therefore it is inefficient. An incremental convex hull algorithm can maintain the convex hull at each insertion performing a trivial modification to the existing convex hull without constructing the convex hull from the scratch. The optimal time complexity for insertion of a point in existing incremental convex hull algorithms is O (n). A new incremental convex hull algorithm with O (h2) time complexity is proposed in this paper. Note that h represents the number of vertices of the convex hull. A set of line segments is used to represent the convex hull. Some of the existing line segments may be deactivated instead of deleting upon the successive growth of the convex hull. Thus, the computational cost is reduced. The proposed algorithm is faster than the existing algorithms when h < SQRT (n) and the concept can be extended to three dimensions.
How to Cite: Wijeweera, K. R., & Kodituwakku, S. R. (2021). An efficient planar incremental convex hull algorithm to find the edges of the boundary polygon of the convex hull of a set of points. Ceylon Journal of Science, 50(3), 261–268. DOI: http://doi.org/10.4038/cjs.v50i3.7907
Published on 06 Sep 2021.
Peer Reviewed

Downloads

  • PDF (EN)

    comments powered by Disqus