Neural networks for convex hull computation
Authors:
- Jiang-She ZhangJZJiang-She Zhang
- Zong-Ben XuZXZong-Ben Xu
- 1 May 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Neural Networks
- Vol. 8 (3) , 601-611
Abstract
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/sup -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.Keywords
This publication has 26 references indexed in Scilit:
- Constructing strongly convex approximate hulls with inaccurate primitivesAlgorithmica, 1993
- Fast geometric approximation techniques and geometric embedding problemsTheoretical Computer Science, 1992
- Gross motion planning—a surveyACM Computing Surveys, 1992
- Geometric clusteringsJournal of Algorithms, 1991
- Theoretical Foundations of Computer Graphics and CAD1988
- Computating the width of a set1985
- Approximation algorithms for convex hullsCommunications of the ACM, 1982
- Determining the minimum-area encasing rectangle for an arbitrary closed curveCommunications of the ACM, 1975
- An efficient algorith for determining the convex hull of a finite planar setInformation Processing Letters, 1972
- On the Distribution of the Bivariate RangeTechnometrics, 1967