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
ABSTRACT
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.
Journal: Journal of Computational Geometry
ISSN 1920-180X
Volume: 2;
Issue: 1;
Start page: 1;
Date: 2011;
Original page
ABSTRACT
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.
