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}, |
| Keywords: | |
| Projects |
Idiap |
| Authors | |
| Editors | |
| Added by: | [UNK] |
| Total mark: | 0 |
|
Attachments
|
|
|
|
|
Notes
|
|
|
|
|
