The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2

DOI10.1007/BF02187778zbMath0712.52009OpenAlexW2066191916MaRDI QIDQ748891

Micha Sharir, Herbert Edelsbrunner

Publication date: 1990

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

Full work available at URL: https://eudml.org/doc/131105

zbMATH Keywords

transversalgeometric permutationmaximum number

Mathematics Subject Classification ID

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

Related Items (24)

Geometric permutations of non-overlapping unit balls revisited ⋮ INFLATING BALLS IS NP-HARD ⋮ Geometric permutations of higher dimensional spheres ⋮ On the two-dimensional Davenport-Schinzel problem ⋮ The overlay of lower envelopes and its applications ⋮ Allowable interval sequences and line transversals in the plane ⋮ Geometric permutations of balls with bounded size disparity. ⋮ On neighbors in geometric permutations. ⋮ On \(k\)-convex polygons ⋮ Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences ⋮ Covering convex sets with non-overlapping polygons ⋮ Algorithms for high dimensional stabbing problems ⋮ Counting pattern-free set partitions. I: A generalization of Stirling numbers of the second kind ⋮ On \(k\)-sets in arrangements of curves and surfaces ⋮ Allowable interval sequences and separating convex sets in the plane ⋮ The different ways of stabbing disjoint convex sets ⋮ Suballowable sequences and geometric permutations ⋮ Geometric orderings of intersecting translates and their applications ⋮ The combinatorial encoding of disjoint convex sets in the plane ⋮ Geometric permutations of disjoint unit spheres ⋮ Some Discrete Properties of the Space of Line Transversals to Disjoint Balls ⋮ Unnamed Item ⋮ The complexity and construction of many faces in arrangements of lines and of segments ⋮ Polyhedral line transversals in space

Cites Work

• A survey of vertical handover decision algorithms in fourth generation heterogeneous wireless networks
• Some dynamic computational geometry problems
• Geometric permutations and common transversals
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Almost linear upper bounds on the length of general Davenport-Schinzel sequences
• Stabbing line segments
• Geometric permutations for convex sets
• On certain functions connected with polynomials in a Galois field

This page was built for publication: The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2