Academic Journals Database
Disseminating quality controlled scientific knowledge

Connected Rectilinear Graphs on Point Sets

Author(s): Maarten Löffler | Elena Mumford

Journal: Journal of Computational Geometry
ISSN 1920-180X

Volume: 2;
Issue: 1;
Start page: 1;
Date: 2011;
Original page

Let V be a set of n points in Rd. We study the question whether there exists an orientation such that V is the vertex set of a connected rectilinear graph in that orientation. A graph is rectilinear if its edges are straight line segments in d pairwise perpendicular directions. We prove that at most one such orientation can be possible, up to trivial rotations of 90 degrees around some axis. In addition, we present an algorithm for computing this orientation (if it exists) in O(nd) time when d≥2.
RPA Switzerland

Robotic Process Automation Switzerland


Tango Jona
Tangokurs Rapperswil-Jona