Vertex Configurations and Their Relationship on Orthogonal Pseudo-Polyhedra
Vertex configuration for a vertex in an orthogonal
pseudo-polyhedron is an identity of a vertex that is determined by the
number of edges, dihedral angles, and non-manifold properties
meeting at the vertex. There are up to sixteen vertex configurations
for any orthogonal pseudo-polyhedron (OPP). Understanding the
relationship between these vertex configurations will give us insight
into the structure of an OPP and help us design better algorithms for
many 3-dimensional geometric problems. In this paper, 16 vertex
configurations for OPP are described first. This is followed by a
number of formulas giving insight into the relationship between
different vertex configurations in an OPP. These formulas
will be useful as an extension of orthogonal polyhedra usefulness on
pattern analysis in 3D-digital images.
[1] D. Ayala and J. Rodriquez, "Connected component labeling based on the
EVM Model," in The 18th spring conference on Computer graphics,
2002, pp. 63-71.
[2] B. Yip and R. Klette, "Angle Counts for Isothetic Polygons and
Polyhedra," Pattern Recognition Letter, vol. 24, pp. 1275-1278, 2003.
[3] A. Aquilera and D. Ayala, "Solving point and plane vs orthogonal
polyhedra using the extreme vertices model (EVM)," presented at the
The Sixth International Conference in Central Europe on Computer
Graphics and Visualization'98, 1998.
[4] J. Czyzowicz, et al., "Illuminating rectangles and triangles in the plane,"
Journal of Combinatorial Theory Series B archive, vol. 57, 1993.
[5] M. d. Berg, et al., Computational Geometry, Second ed.: Springer, 2000.
[6] F. P. Preparata and M. I. Shamos, Computational Geometry an
Introduction. New York: Springer-Verlag, 1985.
[7] K. Tang and T. C. Woo, "Algorithmic aspects of alternating sum of
volumes. Part 1: Data structure and difference operation," Computer-
Aided Design, vol. 23, pp. 357-366, June 1991.
[8] J. R. Rossignac and A. A. G. Requicha, "Construcitve Non-Regularized
Geometry," Computer - Aided Design, vol. 23, pp. 21-32, 1991.
[9] H. S. M. Coxeter, Regular polytopes. New York: Dover Publications,
1973.
[10] J. D. Foley, et al., Computer Graphics: Principles and Practice in C, 2nd
edition ed.: Addison-Wesley, 1996.
[11] T. Biedl and B. Genc, "Reconstructing orthogonal polyhedra from
putative vertex sets," technical reports, 2007.
[12] R. Juan-Arinyo, "Domain extension of isothetic polyhedra with minimal
CSG representation," Computer Graphics Forum, vol. 5, pp. 281-293,
1995.
[13] K. Voss, Discrete Images, Objects, and Functions in Zn. Berlin:
Springer, 1993.
[14] S. L. Senk, Advanced Algebra. Chicago: Scott Foresman/Addison
Wesley, 1998.
[1] D. Ayala and J. Rodriquez, "Connected component labeling based on the
EVM Model," in The 18th spring conference on Computer graphics,
2002, pp. 63-71.
[2] B. Yip and R. Klette, "Angle Counts for Isothetic Polygons and
Polyhedra," Pattern Recognition Letter, vol. 24, pp. 1275-1278, 2003.
[3] A. Aquilera and D. Ayala, "Solving point and plane vs orthogonal
polyhedra using the extreme vertices model (EVM)," presented at the
The Sixth International Conference in Central Europe on Computer
Graphics and Visualization'98, 1998.
[4] J. Czyzowicz, et al., "Illuminating rectangles and triangles in the plane,"
Journal of Combinatorial Theory Series B archive, vol. 57, 1993.
[5] M. d. Berg, et al., Computational Geometry, Second ed.: Springer, 2000.
[6] F. P. Preparata and M. I. Shamos, Computational Geometry an
Introduction. New York: Springer-Verlag, 1985.
[7] K. Tang and T. C. Woo, "Algorithmic aspects of alternating sum of
volumes. Part 1: Data structure and difference operation," Computer-
Aided Design, vol. 23, pp. 357-366, June 1991.
[8] J. R. Rossignac and A. A. G. Requicha, "Construcitve Non-Regularized
Geometry," Computer - Aided Design, vol. 23, pp. 21-32, 1991.
[9] H. S. M. Coxeter, Regular polytopes. New York: Dover Publications,
1973.
[10] J. D. Foley, et al., Computer Graphics: Principles and Practice in C, 2nd
edition ed.: Addison-Wesley, 1996.
[11] T. Biedl and B. Genc, "Reconstructing orthogonal polyhedra from
putative vertex sets," technical reports, 2007.
[12] R. Juan-Arinyo, "Domain extension of isothetic polyhedra with minimal
CSG representation," Computer Graphics Forum, vol. 5, pp. 281-293,
1995.
[13] K. Voss, Discrete Images, Objects, and Functions in Zn. Berlin:
Springer, 1993.
[14] S. L. Senk, Advanced Algebra. Chicago: Scott Foresman/Addison
Wesley, 1998.
@article{"International Journal of Information, Control and Computer Sciences:63761", author = "Jefri Marzal and Hong Xie and Chun Che Fung", title = "Vertex Configurations and Their Relationship on Orthogonal Pseudo-Polyhedra", abstract = "Vertex configuration for a vertex in an orthogonal
pseudo-polyhedron is an identity of a vertex that is determined by the
number of edges, dihedral angles, and non-manifold properties
meeting at the vertex. There are up to sixteen vertex configurations
for any orthogonal pseudo-polyhedron (OPP). Understanding the
relationship between these vertex configurations will give us insight
into the structure of an OPP and help us design better algorithms for
many 3-dimensional geometric problems. In this paper, 16 vertex
configurations for OPP are described first. This is followed by a
number of formulas giving insight into the relationship between
different vertex configurations in an OPP. These formulas
will be useful as an extension of orthogonal polyhedra usefulness on
pattern analysis in 3D-digital images.", keywords = "Orthogonal Pseudo Polyhedra, Vertex configuration", volume = "5", number = "5", pages = "531-8", }