JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]


Journal of Information Science and Engineering, Vol. 29 No. 2, pp. 379-392


A New Concave Hull Algorithm and Concaveness Measure for n-dimensional Datasets


JIN-SEO PARK AND SE-JONG OH
Department of Nanobiomedical Science
WCU Research Center of Nanobiomedical Science
Dankook University
Cheonan, 330-714 Korea

 


    Convex and concave hulls are useful concepts for a wide variety of application areas, such as pattern recognition, image processing, statistics, and classification tasks. Concave hull performs better than convex hull, but it is difficult to formulate and few algorithms are suggested. Especially, an n-dimensional concave hull is more difficult than a 2- or 3-dimensional one. In this paper, we propose a new concave hull algorithm for n-dimensional datasets. It is simple but creative. We show its application to dataset analysis. We also suggest a concaveness measure and a graph that captures geometric shape of an n-dimensional dataset. Proposed concave hull algorithm and concaveness measure/graph are implemented using java, and are posted to http://user.dankook.ac.kr/ ~bitl/dkuCH.


Keywords: convex hull, concave hull, classification, dataset analysis, time complexity

  Retrieve PDF document (JISE_201302_11.pdf)