Abstract
A new topological representation of surfaces in higher dimensions, “cell-chains” is developed. The representation is a generalization of Brisson’s cell-tuple data structure. Cell-chains are identical to cell-tuples when there are no degeneracies: cells or simplices with identified vertices. The proof of correctness is based on axioms true for maps, such as those in Brisson’s cell-tuple representation. A critical new condition (axiom) is added to those of Lienhardt’s n-G-maps to give “cell-maps”. We show that cell-maps and cell-chains characterize the same topological representations.
This work was supported in part by the National Science Foundation under grants CCR-9902091, CCR-9706572, ACI 0086093, CCR-0085982 and CCR-0122581.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baumgardt, B.: Winged-edge polyhedron representation. Technical Report CS-320, Stanford University (1972)
Bern, M., Eppstein, D., Agarwal, P.K., Amenta, N., Chew, P., Dey, T., Dobkin, D.P., Edelsbrunner, H., Grimm, C., Guibas, L.J., Harer, J., Hass, J., Hicks, A., Johnson, C.K., Lerman, G., Letscher, D., Plassmann, P., Sedgwick, E., Snoeyink, J., Weeks, J., Yap, C., Zorin, D.: Emerging challenges in computational topology (1999)
Brisson, E.: Representing geometric structures in d dimensions: Topology and order. In: Symposium on Computational Geometry, pp. 218–227 (1989)
Brisson, E.: Representing geometric structures in d dimension: Topology and order. Discrete and Computational Geometry 9, 387–426 (1993)
Bryant, R., Singerman, D.: Foundations of the theory of maps on surfaces with boundaries. Quarterly Journal of Mathematics 2(36), 17–41 (1985)
Cardoze, D., Cunha, A., Miller, G., Phillips, T., Walkington, N.: A Bezier-Based Approach to Unstructured Moving Meshes. In: 20th Symposium on Computational Geometry (2004)
Deville, M.O., Fischer, P.F., Mund, E.H.: High-Order Methods for Incompressible Fluid Flow. Cambridge University Press, Cambridge (2002)
Dobkin, D., Laszlo, M.: Primitives for the manipulation of three-dimensional subdivisions. In: Third ACM Symosium on Computational Geometry, pp. 86–99 (1987)
Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer, New York (1987)
Edmonds, J.R.: A combinatorial representation for polyhedral surfaces. Notices Amer. Mac. Soc. 7 (1960)
Farouki, R.T.: Closing the gap between cad model and downstream application. SIAM News 32(5) (June 1999)
Guibas, L., Stolfi, J.: Primitives for the manipulation of general subdivisions an the computation of voronoi diagrams. ACM Transactions on Graphics 4(2), 74–123 (1985)
Halperin: Arrangements. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry. CRC Press, Boca Raton (1997)
Hoppe, H.: Progressive meshes. In: ACM SIGGRAPH, pp. 99–108 (1996)
Janich, K.: Topology. Springer, Heidelberg (1984)
Kinsey, L.C.: Topology of Surfaces. Springer, Heidelberg (1993)
Lienhardt, P.: Topological models for boundary representation: a comparison with n-dimensional generalized maps. Computer-Aided Design 23, 59–82 (1991)
Lienhardt, P.: N-dimensional generalized combinatorial maps and cellular quasi-manifolds. International Journal of Computational Geometry & Applications 4, 275–324 (1994)
Lage, M., Lewiner, T., Lopes, H., Velho, L.: Chf: A scalable topological data structure for tetrahedral meshes. In: Proceedings of the XVIII Brazilian Symposium on Computer Graphics and Image Processing, pp. 349–356. IEEE Press, Los Alamitos (2005)
Lèvy, B., Mallet, J.-L.: Cellular modeling in arbitrary dimension using generalized maps
Lundell, A., Weingram, S.: The Topology of CW Complexes. Van Nostrand Reinhold (1969)
Mäntylä: An Introduction to Solid Modeling. Computer Science Press, Inc., Rockville (1988)
Markov, A.A.: Insolubility of the problem of homeomorphy. In: Proceedings of the International Congress of Mathematics, pp. 300–306 (1958); Engish Translation by Afra Zomorodian
Moise, E.: Geometric Topology in Dimensions 2 and 3. Springer, Heidelberg (1977)
Piccinini, R., Fritsch, R.: Cellular Structures in Topology, Cambridge (1990)
Rossignac, J., O’Conner, M.: Sgc: A dimension independent model for pointers with internal structures and incomplete boundaries. In: IFIP/NSF Workshop on Geometric Modeling, pp. 145–180 (1989)
Rossignac, J.: Structured topological complexes: A featured-based api for non-manifold topologies. In: ACM Symposium on Solid Modeling and Applications, pp. 1–9 (1997)
The Sangria Project. Supported by NSF ITR ACI-0086093, http://cs.cmu.edu/~sangria
Schleimer, S.: Sphere recognition lies in NP, http://front.math.ucdavis.edu/math.GT/0407047
Tits, J.: A local approach to buildings. In: Davis, C., Grümbaum, B., Sherk, F.A. (eds.) The Geometric Vein, pp. 519–547. Springer, Heidelberg (1981)
The tumble software package. Supported by NSF ITR ACI-0086093, http://rioja.sangria.cs.cmu.edu/
Tutte, W.T.: What is a map? In: New Directions in the Theory of Graphs, pp. 309–325. Acad. Press, San Diego (1973)
Tutte, W.T.: Graph Theory. Cambridge University Press, Cambridge (1984)
Vince, A.: Combinatorial maps. Journal of Combinatorial Theory B 34, 1–21 (1983)
Vince, A.: Regular combinatorial maps. Journal of Combinatorial Theory B 34, 256–277 (1983)
Volodin, I.A., Kuznetsov, V.E., Fomenko, A.T.: The problem of discriminating the standard sphere. Russian Mathematical Surveys 29(5), 71–172 (1974)
Weiler, K.: Edge-based data structures for solid modeling in curve-surface environment. IEEE Computer Graphics and Applictions 5(1), 21–40 (1985)
Weiler, K.: Topological Structures for Geometric Modeling. PhD thesis, Rensselaer Polytechnic Institute, Troy. N.Y. (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cardoze, D.E., Miller, G.L., Phillips, T. (2006). Representing Topological Structures Using Cell-Chains. In: Kim, MS., Shimada, K. (eds) Geometric Modeling and Processing - GMP 2006. GMP 2006. Lecture Notes in Computer Science, vol 4077. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11802914_18
Download citation
DOI: https://doi.org/10.1007/11802914_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-36711-6
Online ISBN: 978-3-540-36865-6
eBook Packages: Computer ScienceComputer Science (R0)