Abstract
We construct a family ofn disjoint convex set in ℝd having (n/(d−1))d−1 geometric permutations. As well, we complete the enumeration problem for geometric permutations of families of disjoint translates of a convex set in the plane, settle the case for cubes in ℝd, and construct a family ofd+1 translates in ℝd admitting (d+1)!/2 geometric permutations.
Article PDF
Similar content being viewed by others
References
L. Danzer, B. Grünbaum, and V. Klee,Helley's Theorem and Its Relatives, Proceedings of Symposia in Pure Mathematics, Vol. 7, American Mathematical Society, Providence, RI, 1962, pp. 101–180.
H. Edelsbrunner and M. Sharir, The maximum number of ways to stabn convex nonintersecting objects in the plane is 2n−2,Discrete Comput. Geom. 5 (1990), 35–42.
B. Grünbaum, On common transversals,Arch. Math. 9 (1958), 465–469.
H. Hadwiger, H. Debrunner, and V. Klee,Combinatorial Geometry in the Plane, Holt, Rinehart and Winston, New York, 1964.
M. Katchalski, A conjecture of Grünbaum on common transversals,Math. Scand. 59 (1986), 192–198.
M. Katchalski, T. Lewis, and A. Liu, Geometric permutations and common transversals,Discrete Comput. Geom. 1 (1986), 371–377.
M. Katchalski, T. Lewis, and A. Liu, Geometric permutations of disjoint translates of convex sets,Discrete Math. 65 (1987), 249–259.
M. Katchalski, T. Lewis, and J. Zaks, Geometric permutations for convex sets,Discrete Math. 54 (1985), 271–284.
H. Tverberg, Proof of Grünbaum's conjecture on common transversals for translates,Discrete Comput. Geom. 4 (1989), 191–203.
R. Wenger, Upper bounds on geometric permutations,Discrete Comput. Geom. 5 (1990), 27–33.
Author information
Authors and Affiliations
Additional information
This research was partly supported by NSERC Grants A3062, A5137, and A8761.
Rights and permissions
About this article
Cite this article
Katchalski, M., Lewis, T. & Liu, A. The different ways of stabbing disjoint convex sets. Discrete Comput Geom 7, 197–206 (1992). https://doi.org/10.1007/BF02187836
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187836