International audience

Let S be a finite set of n points in the plane in general position. We prove that every inclusion-maximal family of subsets of S separable by convex pseudo-circles has the same cardinal (n 0)+(n 1)+(n 2)+(n 3). This number does not depend on the configuration of S and is the same as the number of subsets of S separable by true circles. Buzaglo, Holzman, and Pinchasi already showed that it is an upper bound for the number of subsets separable by (non necessarily convex) pseudo-circles.

Araucarias have been introduced by Schott and Spehner as trees which appear in the minimal automaton of the shuffle of words. We give here a new definition of araucarias which is more constructive and we prove that our definition of araucarias is equivalent to the original one. From the new definition we derive an optimal algorithm for the construction of araucarias and a new method for calculating their size. Moreover we characterize araucarias by properties of their maximal paths, by associating a capacity to every edge. We then show that every araucaria can be obtained by grafting and merging smaller araucarias. We prove also that every directed tree can be embedded in an araucaria. Moreover we define a capacity for every vertex of an araucaria, which leads to different new enumeration formulas for araucarias.