doi: 10.7763/IJCTE.2015.V7.1008
Computing Convex Layers of a Dynamic Point Set
- 1National Institute of Technology, Durgapur, India 713209
- 2Department of Computer Science, Dronacharya College of engineering, Gurgaon, Haryana.
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(<em>n</em>log<em>n</em>) time. However, to solve dynamic version of the problem the suggested algorithm requires O(<em>n</em><sup>2</sup>) time for a set of <em>n</em> points.
Keywords
- Computational geometry
- convex hull
- convex layers
- incremental algorithm
- tangent
How to 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. https://doi.org/10.7763/IJCTE.2015.V7.1008
Copyright & License
Copyright © 2015 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).