Research Repository

Permanent URI for this community

http://nits.ndl.gov.in/handle/123456789/32

Browse

Browsing Research Repository by Author "Agre, Ankit"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Discrete medial axis extraction using discrete voronoi diagram
    (Department of Computer Science & Engineering, NITS, 2022) Agre, Ankit
    Voronoi diagram is one of the classical problems in Computational Geometry. Given a set of sites it partitions the plane into subdivisions or regions corresponding to each site such that any point in a given region is nearest to the (Xn-responding site contained in that region. It is One Of the few interdisciplinary concepts with relevant material to found in, but not limited to, astronomy, biology, geography, medical sciences, urban and regional planning so researchers have tried to develop algorithm for computing Voronoi diagram the middle of 20th century. The most common algorithm available in the literature is the Incremental algorithm which is of O(n2) complexity and relatively easy to implement, the Divide and Conquer approach with O(nlogn) complexity and the Fortune's algorithm with complexity O(nlogn) and is by far the optimal solution. But the main problem with all above mentioned algorithms is that they fail to perform with the same accuracy when on discrete space This is because when we compute a Discrete Voronoi diagram we have to consider a finite domain (reptBentecl as a uniform grid) such that the Discrete Voronoi region of site is the finite set of cells closer to that site than any other. Thus, to solve the problem we have a parallel algorithm for the construction of discrete voronoi diagram. Moreover, we have also proposed an algorithm for the extraction of discrete medial axis based on the discrete voronoi diagram. We have also mentioned the applicability of discrete axis for the efficient reconstruction of 3D surface.