We propose a novel Voronoi Diagram based skeletonization algorithm that produces non-centered skeletons. The first strategy considers utilizing Elliptical Line Voronoi Diagrams with varied density based sampling of the polygonal shapes. The second strategy applies a weighting scheme on Elliptical Line Voronoi Diagrams and Line Voronoi Diagrams. The proposed skeletonization algorithm uses precomputed distance fields and basic element-wise operations, thus can be easily adapted for parallel execution. Non-centered Voronoi Skeletons give a representation that is more similar to real world skeletons and retain many of the desirable properties of skeletons.