Representing orders on the plane by translating convex figures
type: Item
instance of: scholarly article
title: Representing orders on the plane by translating convex figures
zbMATH Open document ID: 0663.06004
DOI: 10.1007/BF00714475
author: Ivan Rival
author: J. Urrutia
published in: Order
publication date: 1988-01-01T00:00:00Z
review text: Suppose each figure in a finite collection of disjoint convex plane figures is assigned a single direction of motion not necessarily all the same. We say that the figure B obstructs the figure A if there is a line joining a point of A to a point of B which follows the direction assigned to A. Then a blocking relation is defined such that B blocks A if there is a sequence \(A=A_ 1,...A_ k=B\) with each \(A_{i+1}\) obstructing \(A_ i\). We call the relation m-directional if each of the figures is assigned one of m directions. The following three theorems are proved. 1. There is a one-to-one correspondence between the class of all one- directional blocking relations and the class of all truncated planar lattices. A lattice is planar if its diagram can be drawn without any crossing lines. It is truncated when its greatest and least elements are removed. 2. Every ordered set has a subdivision which can be represented as a two- directional blocking relation. 3. There is an ordered set which has no m-directional representation for any positive integer m.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 68U20
zbMATH DE Number: 4083689
zbMATH Keywords: separability
zbMATH Keywords: robotics
zbMATH Keywords: motion planning
zbMATH Keywords: convex plane figures
zbMATH Keywords: blocking relation
zbMATH Keywords: truncated planar lattices
MaRDI profile type: Publication
cites work: Colouring lattices
cites work: Q3217599
cites work: On Removing a Ball without Disturbing the Others
cites work: Graph Theory and Probability
cites work: Q5786239
cites work: On the dimension of partially ordered sets
cites work: Fundamentals of planar ordered sets
cites work: Planar Lattices
cites work: Combinatorial partitions of finite posets and lattices - Ramsey lattices
cites work: Representing orders on the plane by translating points and lines
cites work: Q3683086
cites work: Q3716330
cites work: Bemerkungen zum Vierfarbenproblem
full work available at URL: https://doi.org/10.1007/bf00714475
OpenAlex ID: W2050272393
description: scientific article; zbMATH DE number 4083689