On the boundary of the union of planar convex sets

DOI10.1007/PL00009424MaRDI QIDQ1289237zbMATH OpenOpenAlexFDO

Authors János Pach, Micha Sharir

Publication date 6 December 1999

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/pl00009424

zbMATH Keywords

arcsboundariesinequalitiesplanar convex setsregular and irregular vertices

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Inequalities and extremum problems involving convexity in convex geometry (52A40)

Review text

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.

Recommendations

• On regular vertices on the union of planar objects
• On the number of regular vertices of the union of Jordan regions
• On the number of regular vertices of the union of Jordan regions
• Tangencies between families of disjoint regions in the plane
• On regular vertices of the union of planar convex objects
• Tangencies between families of disjoint regions in the plane
• Convex polygons in geometric triangulations
• The number of edges of many faces in a line segment arrangement
• Convex partial transversals of planar regions
• Crossing families

Cited in

(17)

• On regular vertices of the union of planar convex objects
• The common exterior of convex polygons in the plane
• On the complexity of barrier resilience for fat regions and bounded ply
• Coloring intersection hypergraphs of pseudo-disks
• Approximate unions of lines and Minkowski sums
• On regular vertices on the union of planar objects
• On the convex layers of a planar set
• Tangencies between families of disjoint regions in the plane
• Union of random Minkowski sums and network vulnerability analysis
• On the number of regular vertices of the union of Jordan regions
• Coloring intersection hypergraphs of pseudo-disks
• On the union of convex bodies with no interior point in common
• On the number of regular vertices of the union of Jordan regions
• Vertex classification of planar \(C\)-polygons
• On the number of tangencies among 1-intersecting curves (extended abstract)
• Strong Hanani-Tutte for the torus
• On boundary arcs joining antipodal points of a planar convex body

This page was built for publication: On the boundary of the union of planar convex sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1289237)