Abstract
Given a finite collection of disjoint, convex figures on the plane, is it possible to assign to each a single direction of motion so that this collection of figures may be separated, through an arbitrary large distance, by translating each figure one at a time, along its assigned direction? We present a computational model for this separability problem based on the theory of ordered sets.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
B.Bollobas (1977) Colouring lattices,Alg. Univ. 7, 313–314.
B. Chazelle, T. Ottmann, E. Soisalon-Soininen, and D. Wood (1983) The complexity and decidability of separation, Tech. Report CS-83-34, University of Waterloo.
R.Dawson (1984) On removing a ball without disturbing the others,Math. Mag. 57, 27–30.
P.Erdös (1959) Graph theory and probability,Canad. J. Math. 11, 34–38.
I.Fáry (1948) On the straight line representation of planar graphs,Acta. Sci. Math. (Szeged) 11, 229–233.
L. J. Guibas and F. F. Yao (1980) On translating a set of rectangles,Proc. 12th Annual ACM Symposium Th. of Comp., pp. 154–160.
D.Kelly (1981) On the dimension of partially ordered sets,Discrete Math. 35, 135–156.
D. Kelly (1987) Fundamentals of planar ordered sets,Discrete Math.
D.Kelly and I.Rival (1975) Planar lattices,Canad. J. Math. 27, 636–665.
M. Mansouri and G. T. Toussaint (1985) Translation queries for convex polygons,Proc. IASTED Internat. Sympos. Robotics and Automation., Lugano, Switzerland.
J.Nešetřil and V.Rödl (1984) Combinatorial partitions of finite posets and lattices-Ramsey lattices,Alg. Univ. 19, 106–119.
R. Nowakowski, I. Rival, and J. Urrutia (1987) Representing orders on the plane by translating points and lines, to appear.
J.-R. Sack and G. T. Toussaint (1985) Translating polygons in the plane,Proc. STACS '85, Saarbrücken, pp. 310–321.
G. T.Toussaint (1985) Movable separability of sets, inComputational Geometry (G. T.Toussaint, ed.), North Holland, Amsterdam, pp. 335–376.
B.Sands (1985) Problem 2.7, inGraphs and Order (ed. I.Rival), D. Reidel, Dordrecht, p. 531.
G. X. Viennot (1985) Problèmes combinatoires posés par la physique statistique, Séminaire Bourbaki, No. 626, inAstérisque, No. 121-122 225-246.
K.Wagner (1936) Bemerkungen zum Vierfarbenproblem,Jber. Deutsch. Math. Verein. 46, 26–32.
Author information
Authors and Affiliations
Additional information
Communicated by P. Hell
Rights and permissions
About this article
Cite this article
Rival, I., Urrutia, J. Representing orders on the plane by translating convex figures. Order 4, 319–339 (1988). https://doi.org/10.1007/BF00714475
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF00714475