Reconstructing orthogonal polyhedra from putative vertex sets (Q634249): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 09:19, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Reconstructing orthogonal polyhedra from putative vertex sets |
scientific article |
Statements
Reconstructing orthogonal polyhedra from putative vertex sets (English)
0 references
2 August 2011
0 references
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.
0 references
reconstruction
0 references
vertex set
0 references
orthogonal polyhedra
0 references
pattern recognition
0 references
object recognition
0 references