< Retour au sommaire

Primal and dual approaches for the enumeration of hyperplane arrangements

Baptiste Plaquevent-Jourdain le

Lieu: Salle 1073

Suivre en visio

Abstract

Hyperplane arrangements is a topic from combinatorial and computational geometry with a long history at least started two centuries ago. It appears in various theoretical and applied contexts, such as nonsmooth analysis, robot path planning, quantum physics and computer science, beyond other geometric problems. This talk discusses the (numerical) enumeration of the chambers of arrangements, i.e., the connected components of the space without the hyperplanes, which is one of the main question about arrangements.

Before delving into numerical considerations, we mention various properties, good to keep in mind when designing algorithms, of the chambers of arrangements. These include discussions on symmetry, nature of arrangements, particular configurations and some illustrations of the relations with other topics, especially with computer science and neural networks.

Relatively surprisingly, there are not that many algorithms to identify the chambers of an arrangement. We discuss some of them before delving deeper into a recent one by Rada and Černý that was shown to improve on previous ones. Several modifications / improvements, using for instance duality and matroid circuits, are discussed and benchmarked. Finally, we consider one extension of this work, the problem of obtaining the whole the arrangement and not only the chambers.