International Journal of Computer Theory and Engineering

Frequency: Quarterly
ISSN: 1793-8201 (Print), 2972-4511 (Online)
Publisher:IACSIT Press

OPEN ACCESS
4.0
CiteScore

IJIET 2015 Vol.7(6): 495-498
doi: 10.7763/IJCTE.2015.V7.1008

Computing Convex Layers of a Dynamic Point Set

Sanjib Sadhu1,2 , Niraj Kumar

  • 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
1008-TD013

How to Cite

Copied

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).

Article Metrics in Dimensions

Menu