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
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    planar convex sets
    0 references
    double-permutation sequence
    0 references
    geometric permutation
    0 references
    pseudoline arrangement
    0 references
    0 references
    0 references