The iterated difference of polyhedra has been proposed independently in [Zwie-Aart-Wess92] and [Shon93] as a sufficient condition for to be exactly computable by a two-layered neural network. An algorithm checking whether included in 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.
Florian Frédéric Vincent Breider, Myriam Borgatta