DOI: 10.7763/IJCTE.2015.V7.1008
Computing Convex Layers of a Dynamic Point Set
Abstract—The convex layers of a given point set can be computed by iterative process of finding convex hull after discarding the points of already computed convex hull. Computation of convex layers has been widely studied in the static environment where the point set are fixed. In this paper, we propose an idea to compute set of convex layers in dynamic context. There exists an optimal time algorithm to solve the static version of the problem in O(nlogn) time. However, to solve dynamic version of the problem the suggested algorithm requires O(n2) time for a set of n points.
Index Terms—Computational geometry, convex hull, convex
layers, incremental algorithm, tangent.
Sanjib Sadhu is with the Department of Computer Science, National
Institute of Technology, Durgapur, India 713209 (e-mail:
sanjibsadhu411@gmail.com).br />
Niraj Kumar was with the National Institute of Technology, Durgapur,
India 713209. He is now with the Department of Computer Science,
Dronacharya College of engineering, Gurgaon, Haryana (e-mail:
nirajcse08@gmail.com).
Cite:Sanjib Sadhu and Niraj Kumar, "Computing Convex Layers of a Dynamic Point Set," International Journal of Computer Theory and Engineering vol. 7, no. 6, pp. 495-498, 2015.