On the boundary of the union of planar convex sets (Q1289237)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On the boundary of the union of planar convex sets
scientific article

    Statements

    On the boundary of the union of planar convex sets (English)
    0 references
    0 references
    0 references
    6 December 1999
    0 references
    Let \(\mathcal C\) be a collection of \(n \geq 3\) nondegenerate convex sets in the plane, any two of which have at most a finite number of boundary points in common. If two members of \(\mathcal C\) have exactly two boundary points in common, then these points are called regular vertices of the arrangement \(\mathcal A(\mathcal C).\) All other intersection points of the boundary curves are said to be irregular. Let \(U =\cup \mathcal C\) denote the union of all members of \(\mathcal C.\) Let \(R\) and \(I\) denote the set of regular and irregular vertices of \(\mathcal A(\mathcal C),\) respectively, lying on \(\partial U,\) the boundary of \(U.\) Further, put \(V= R\cup I.\) If the sets in \(\mathcal C\) are bounded, then \(| V|\) is equal to the number of arcs that compose \(\partial U.\) It was shown in \textit{K. Kedem, R. Livne, J. Pach} and \textit{M. Sharir}, Discrete Comput. Geom. 1, 59-71 (1986; Zbl 0594.52004) that if any two members of \(\mathcal C\) have at most two boundary points in common, then \(| R|= | V|\leq 6n - 12,\) and this bound is tight in the worst case. The authors generalize this result as follows: For any collection of \(n\geq 3\) nondegenerate convex sets in general position in the plane satisfying the above assumptions, the bound \(| R|\leq 2| I|+6n-12\) holds.
    0 references
    planar convex sets
    0 references
    boundaries
    0 references
    regular and irregular vertices
    0 references
    arcs
    0 references
    inequalities
    0 references

    Identifiers