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


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

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

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 ~bitl/dkuCH.

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

Full Text () Retrieve PDF document (201303_11.pdf)

Received August 19, 2010; revised December 4, 2010 & February 18, 2011; accepted February 22, 2011.
Communicated by Jen-Hui Chuang.
* This work was supported by Grant No. R31-2008-000-10069-0 from the World Class University (WCU) project of the Ministry of Education, Science & Technology (MEST) and the Korea Science and Engineering Foundation (KOSEF).