全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

Connected Rectilinear Graphs on Point Sets

Full-Text   Cite this paper   Add to My Lib

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.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133