Criteria for recoverability of rectangular polyhedra in terms of linear programming

DOI IR Web Site Open Access

Bibliographic Information

Other Title
  • 線形計画法を用いた直交多面体の復元可能性の判定
  • センケイ ケイカクホウ オ モチイタ チョッコウ タメンタイ ノ フクゲン カノウセイ ノ ハンテイ
  • センケイ ケイカクホウ オ モチイタ チョッコウ タメンテイ ノ フクゲン カノウセイ ノ ハンテイ

Search this article

Description

A rectangular polyhedron is a polyhedron whose corners consist of three mutually perpendicular faces. In the present paper, we consider the recoverability problem of a rectangular polyhedron from a given labeled line drawing that has certain special properties. Here the labels attached to junctions signify the 3D structures around them. Since the orthogonality constraints are quadratic, that is, not linear and it is hard to deal with, we relax the orthogonality constraints into the parallel constraints so that they become linear. Then our problem is changed to the recoverability of parallel polyhedra. The recoverability of parallel polyhedra is reduced to the existence of a feasible solution of the linear programming problem. Further, we prove that the recoverability of parallel polyhedra is equivalent to that of rectangular polyhedra by constructing a label preserving affine transformation from a parallel polyhedron to a rectangular polyhedron under the suitable conditions for angles between lines in the drawings.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top