Given n points in d-dimensional space, we would like to connect the points with straight line segments to form a connected graph whose edges use d pairwise perpendicular directions. We prove that there exists at most one such set of directions. For d¿=¿2 we present an algorithm for computing these directions (if they exist) in O (n 2) time.
|Title of host publication||Graph Drawing (16th International Symposium, GD'08, Heraklion, Crete, Greece, September 21-24, 2008, Revised Papers)|
|Editors||I.G. Tollis, M. Patrignani|
|Place of Publication||Berlin|
|Publication status||Published - 2009|
|Name||Lecture Notes in Computer Science|