Representing orders on the plane by translating points and lines
type: Item
instance of: scholarly article
title: Representing orders on the plane by translating points and lines
zbMATH Open document ID: 0709.06002
DOI: 10.1016/0166-218X(90)90135-Y
author: Ivan Rival
author: J. Urrutia
author: R. J. Nowakowski
published in: Discrete Applied Mathematics
publication date: 1990-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 4164923
zbMATH Keywords: computational geometry
zbMATH Keywords: separability problem
zbMATH Keywords: convex figures
zbMATH Keywords: m- directional representation of a poset
zbMATH Keywords: blocking relations
zbMATH Keywords: interval order
reviewed by: Cristian Masalagiu
MaRDI profile type: Publication
cites work: Representing orders on the plane by translating convex figures
full work available at URL: 0166-218x(90)90135-y
OpenAlex ID: W2075236554
description: scientific article; zbMATH DE number 4164923