Leung Y, Zhang J S, Xu Z B
Dept. of Geogr., Chinese Univ. of Hong Kong, Shatin.
IEEE Trans Neural Netw. 1997;8(3):601-11. doi: 10.1109/72.572099.
Computing convex hull is one of the central problems in various applications of computational geometry. In this paper, a convex hull computing neural network (CHCNN) is developed to solve the related problems in the N-dimensional spaces. The algorithm is based on a two-layered neural network, topologically similar to ART, with a newly developed adaptive training strategy called excited learning. The CHCNN provides a parallel online and real-time processing of data which, after training, yields two closely related approximations, one from within and one from outside, of the desired convex hull. It is shown that accuracy of the approximate convex hulls obtained is around O[K(-1)(N-1/)], where K is the number of neurons in the output layer of the CHCNN. When K is taken to be sufficiently large, the CHCNN can generate any accurate approximate convex hull. We also show that an upper bound exists such that the CHCNN will yield the precise convex hull when K is larger than or equal to this bound. A series of simulations and applications is provided to demonstrate the feasibility, effectiveness, and high efficiency of the proposed algorithm.
计算凸包是计算几何各种应用中的核心问题之一。本文开发了一种凸包计算神经网络（CHCNN）来解决N维空间中的相关问题。该算法基于一个两层神经网络，在拓扑结构上与ART相似，并采用了一种新开发的称为激发学习的自适应训练策略。CHCNN提供数据的并行在线实时处理，经过训练后，可产生两个紧密相关的近似值，一个来自内部，一个来自外部，近似于所需的凸包。结果表明，所获得的近似凸包的精度约为O[K^(-1)(N - 1)/]，其中K是CHCNN输出层中的神经元数量。当K足够大时，CHCNN可以生成任何精确的近似凸包。我们还表明存在一个上限，当K大于或等于此上限时，CHCNN将产生精确的凸包。提供了一系列模拟和应用来证明所提算法的可行性、有效性和高效性。
