Non-pixel-based skeletonization techniques show many advantages over traditional pixel-based methods such as thinning. These advantages include superior efficiency and faster processing time. Using a Constrained Delaunay Triangulation, an algorithm is presented here that improves upon non-pixel-based methods, through an adaptive selection of contour points. The proposed algorithm uses a new measure for skeletonization error, and aims to reduce this error across entire images, while retaining the significant properties that make a non-pixel-based technique so successful. Results show that the proposed method is computationally efficient, robust against noise, and produces a skeleton that is confirmed by a human?s perception of the image.