The combinatorial encoding of disjoint convex sets in the plane (Q949781)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The combinatorial encoding of disjoint convex sets in the plane |
scientific article |
Statements
The combinatorial encoding of disjoint convex sets in the plane (English)
0 references
21 October 2008
0 references
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.
0 references
planar convex sets
0 references
double-permutation sequence
0 references
geometric permutation
0 references
pseudoline arrangement
0 references
0 references