The combinatorial encoding of disjoint convex sets in the plane (Q949781)

The authors introduce the following combinatorial encoding for a planar family \(\mathcal{C}=\{ C_1,\dots, C_n\}\) of mutually disjoint compact convex sets: Project the members of \(\mathcal {C}\) onto a directed line \(L\) and denote the endpoints of each projected set \(C_i\) by \(i, i'\) according to their order on \(L\). This gives a permutation of the \(2n\) indices \(1,\dots, n, 1',\dots, n'\). Then, rotate \(L\) counterclockwise and record the circular sequence consisting of all the ``double permutations'' of \(1,\dots,n\) arising in this way. Using this encoding, the authors give a new proof of the \textit{H. Edelsbrunner}-\textit{M. Sharir} theorem [Discrete Comput. Geom. 5, No. 1, 35--42 (1990; Zbl 0712.52009)] which asserts that a planar family of \(n\) compact convex sets cannot be met by straight lines in more than \(2n-2\) combinatorially distinct ways. Moreover, the Edelsbrunner-Sharir theorem is extended from families of compact convex sets to families of compact connected sets.