Abstract
LetA be a family ofn pairwise disjoint compact convex sets inR d. Let\(\Phi _d (m) = 2\Sigma _{i = 0}^{d - 1} \left( {_i^{m - 1} } \right)\). We show that the directed lines inR d, d ≥ 3, can be partitioned into\(\Phi _d \left( {\left( {_2^n } \right)} \right)\) sets such that any two directed lines in the same set which intersect anyA′⊆A generate the same ordering onA′. The directed lines inR 2 can be partitioned into 12n such sets. This bounds the number of geometric permutations onA by 1/2φ d ford≥3 and by 6n ford=2.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
B. Grunbaum,Convex Polytopes (Wiley, New York, 1967).
F. Harary,Graph Theory (Addison-Wesley, Reading, Massachusetts, 1969).
M. Katchalski. On a Conjecture of Grunbaum on Common Transversals, to appear inMathematica Scandinavica.
M. Katchalski, T. Lewis, and A. Liu, Geometric Permutations and Common Transversals,Discrete and Computational Geometry,1 (1986), 371–377.
M. Katchalski, T. Lewis, and A. Liu, Geometric Permutations of Disjoint Translates of Convex Sets, to appear inDiscrete Mathematics.
M. Katchalski, T. Lewis, and J. Zaks, Geometric Permutations for Convex Sets,Discrete Mathematics,54 (1985), 271–284.
F. P. Preparata and M. I. Shamos,Computational Geometry (Springer-Verlag, New York, 1985).
H. Tverberg, A Separation Property of Plane Convex Sets,Mathematica Scandinavica,45 (1979), 255–260.
R. O. Winder, Partitions ofN-Space by Hyperplanes,SIAM Journal on Applied Mathematics,14 (1966), 811–818.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Wenger, R. Upper bounds on geometric permutations for convex sets. Discrete Comput Geom 5, 27–33 (1990). https://doi.org/10.1007/BF02187777
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187777