Representing orders on the plane by translating points and lines (Q921023): Difference between revisions

One of the most important problems in computational geometry is the separability problem (robot motion without collisions and screen clearing in computer science graphics are instances of the above). \textit{I. Rival} and \textit{J. Urrutia} [Order 4, No.4, 319-339 (1988; Zbl 0663.06004)] have initiated a study of this problem using the theory of ordered sets. In the mentioned paper they introduce the ``blocking'' relation on a collection of disjoint convex figures in the plane (each assigned to one of the m, fixed, directions), which is an order, and define the m- directional representation of a poset P. This study is dedicated to the representation of orders by ``special'' blocking relations (i.e.: particular convex figures - points, lines, segments, and limited - one or two - directions). Four theorems are proved, from which we mention here only one: Every interval order is a line blocking relation requiring at most two directions.