logo Idiap Research Institute        
 [BibTeX] [Marc21]
On the Complexity of Recognizing Iterated Differences of Polyhedra
Type of publication: Conference paper
Citation: Mayo97a1
Booktitle: Proceedings of the International Conference on Artificial Neural Networks (ICANN'97)
Series: Lecture Notes in Computer Science
Number: 1327
Year: 1997
Publisher: Springer-Verlag
Note: IDIAP-RR 97-10
Crossref: mayo97a:
Abstract: The iterated difference of polyhedra $V = P_1 \backslash ( P_2 \backslash (... P_k ) ... )$ has been proposed independently in [Zwie-Aart-Wess92] and [Shon93] as a sufficient condition for $V$ to be exactly computable by a two-layered neural network. An algorithm checking whether $V$ included in $R^d$ is an iterated difference of polyhedra is proposed in [Zwie-Aart-Wess92]. However, this algorithm is not practically usable because it has a high computational complexity and it was only conjectured to stop with a negative answer when applied to a region which is not an iterated difference of polyhedra. This paper sheds some light on the nature of iterated difference of polyhedra. The outcomes are\,: (i) an algorithm which always stops after a small number of iterations, (ii) sufficient conditions for this algorithm to be polynomial and (iii) the proof that an iterated difference of polyhedra can be exactly computed by a two-layered neural network using only essential hyperplanes.
Userfields: ipdmembership={learning},
Projects Idiap
Authors Mayoraz, Eddy
Editors Gerstner, W.
Germond, A.
Hasler, M.
Nicoud, J. -D.
Added by: [UNK]
Total mark: 0
  • rr97-10.pdf
  • rr97-10.ps.gz