Reconstructing orthogonal polyhedra from putative vertex sets (Q634249)

Given a set \(S\) of \(n\) points in 3D space, the problem is to find an orthogonal convex polyhedron for which this is a set of vertices. If it is the intension to characterize the polyhedron only by (some of) its vertices, the uniqueness of the solution is relevant. An \(O(n\log n)\) algorithm is proposed to find a unique solution to the problem (i.e., the orthogonally convex hull of \(S\)). The problem becomes more complex if first a rotation \(S'\) of \(S\) has to be found before the polyhedron is constructed. This requires an \(O(n^2\log n)\) algorithm. In this paper, first an \(O(n\log n)\) algorithm is given to solve the problem in 2D (if the rotation exists, it is unique). Then this is used to solve the problem in 3D with a complexity \(O(n^2\log n)\). Some brief remarks, mostly open problems, are given for the case when additional points (on or inside the polyhedron) are prescribed.