×

Subdivisions de surfaces et cartes généralisées de dimension 2. (Subidivisions of surfaces and generalized maps of dimension 2). (French) Zbl 0734.68095

Summary: This paper deals with modeling subdivisions of orientable surfaces, with or without boundaries. Modeling this kind of subdivisions is of great interest in Boundary Representation.
Following H. G. Griffiths [Surfaces, Cambridge etc.: Cambridge University Press (1981; Zbl 0457.57001)] for instance, we present a constructive definition of subdivisions of surfaces, and a classification of these subdirections into topological surfaces. We also present the notion of topological 2-map, which allows to model the topology of any subdivision of any orientable surface without boundaries, and the notion of 2-G-map, introduced by W. T. Tutte, which allows to model the topology of any subdivsion of any surface (orientable or not, with or without boundaries). Any 2-map can be deduced from a 2-G-map, which defines the topology of a subdivision of an orientable surface without boundaries. Characteristics are associated to any 2-map and to any 2-G-map. These characteristics make it possible to classify 2-maps and 2-G-maps, according to the classification of the subdivisions which are defined by these 2-maps and 2-G-maps. Finally, we present basic operations, which allow to construct any 2-G-map (and consequently, of any 2-map).

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Citations:

Zbl 0457.57001
PDF BibTeX XML Cite
Full Text: DOI EuDML

References:

[1] 1. S. ANSALDI, L. DE FLORIANI et B. FALCIDIENO, Geometric Modeling of Solid Objects by Using a Face Adjacency Graph Representation, Computer Graphics, 1985, 19, n^\circ 3, p. 131-139 (Siggraph’85).
[2] 2. D. ARQUÈS et P. KOCH, Modélisation de solides par les pavages, Proceedings of Pixim’89, Paris, France, 25-29 septembre 1989, p. 47-61 (éditions Hermès).
[3] 3. B. BAUMGART, A Polyhedron Representation for Computer Vision, AFIPS Nat. Conf. Proc., 1975, 44, p. 589-596.
[4] 4. C. BERGE, Graphes et hypergraphes, Dunod, Paris, 1970. Zbl0213.25702 MR357173 · Zbl 0213.25702
[5] 5. E. BRISSON, Representing Geometric Structures in d Dimensions: Topology and order, Proceedings of the 5th A.C.M. Symposium on Computational Geometry, Saarbrücken, R.F.A., 5-7 juin 1989, p. 218-227.
[6] 6. R. CORI, Un code pour les graphes planaires et ses applications, Astérisque, n^\circ 27, 1975. Zbl0313.05115 MR404045 · Zbl 0313.05115
[7] 7. D. DOBKIN et M. LASZLO, Primitives for the Manipulation of Three-Dimensional Subdivisions, Proceedings of the 3th A.C.M. Symposium on Computational Geometry, Waterloo, Canada, 8-10 june 1987, p. 86-99.
[8] 8. J.-F. DUFOURD, Spécification Progressive d’une Algèbre pour Manipuler les Cartes Topologiques Orientées, Proceedings of Pixim ’88, Paris, France, 24-28 octobre 1988, p. 61-80 (éditions Hermès).
[9] 9. J.-F. DUFOURD, C. GROSS et J.-C. SPEHNER, A Digitisation Algorithm for the Entry of Planar Maps, Proceedings of Computer Graphics International’89, Leeds, U.K., 1989, Springer-Verlag.
[10] 10. J.-F. DUFOURD, A Topological Map-Based Kernel for Polyhedron Modellers: Algebraic Specification and Logic Prototyping, Proceedings of Eurographics’89, Hambourg, R.F.A., 4-8 septembre 1989, p. 301-312, North-Holland.
[11] 11. J. EDMONDS, A Combinatorial Representation for Polyhedral Surfaces, Notices Amer. Math. Soc, n^\circ 7, 1970.
[12] 12. H.-B. GRIFFITHS, Surfaces, Cambridge University Press, Cambridge, 2e édition, 1981, édition française : Cedec, 1977. Zbl0457.57001 MR643479 · Zbl 0457.57001
[13] 13. L. GUIBAS et J. STOLFI, Primitives for the Manipulation of General Subdivisions and the Computation of Voronoï Diagrams, A.C.M. Transactions on Graphics, 1985, n^\circ 2, p. 74-123. Zbl0586.68059 · Zbl 0586.68059
[14] 14. A. JACQUE, Constellations et graphes topologiques, Colloque Math. Soc. Janos Bolyai, North-Holland, 1970, p. 657-672. Zbl0213.25901 MR297622 · Zbl 0213.25901
[15] 15. L. JAMES, Maps and Hypermaps: Operations and Symmetry, PhD thesis, Department of Mathematics, University of Southampton, U.K., August 1985.
[16] 16. P. LIENHARDT, Extension of the Notion of Map and Subdivisions of a Three-Dimensional Space, Lecture Notes in Computer Science, n^\circ 294, p. 301-311, Proceedings of the 5th Symposium on the Theoretical Aspects of Computer Science, february 1988, Bordeaux, France. Zbl0654.05026 MR935806 · Zbl 0654.05026
[17] 17. P. LIENHARDT, Subdivisions de surfaces, cartes et S-V-cartes, Research Report R88-4, Department of Computer Science, University Louis Pasteur, Strasbourg, France. · Zbl 0734.68095
[18] 18. P. LIENHARDT, Subdivisions of Surfaces and Generalized Maps, Proceedings of Eurographics’ 89, Hamburg, R.F.A., 4-8 septembre 1989, p. 439-452, North-Holland.
[19] 19. P. LIENHARDT, Subdivisions of N-Dimensional Spaces and N-Dimensional Generalized Maps, Proceedings of the 5th A.C.M. Symposium on Computational Geometry, Saarbrücken, R.F.A., 5-7 juin 1989, p. 228-236.
[20] 20. M. MÄNTYLÄ, Computational Topology: a Study of Topological Manipulations and Interrogations in Computer Graphics and Geometric Modeling, Acta Polytechnica Scandinavia, n^\circ 37, 1983, Helsinski. Zbl0505.68042 MR703203 · Zbl 0505.68042
[21] 21. L. PUTNAM et P. SUBRAHMANYAM, Boolean Operations on N-Dimensional Objects, IEEE Computer Graphics and Applications, Juin 1986, p. 43-51.
[22] 22. A. REQUICHA, Representations for Rigid Solids: Theory, Methods and Systems, Computing Surveys, 1980, 12, n^\circ 4, p. 437-464.
[23] 23. H. SEIFERT et W. THRELFALL, Lehrbuch der Topologie, Chelsea, New York, 1947.
[24] 24. J.-C. SPEHNER, Merging in Maps and Paving, Research Report n^\circ 48, Laboratoire de Mathématiques et Informatique, Université de Haute-Alsace, Mulhouse, France. · Zbl 0733.68093
[25] 25. W. TUTTE, Graph Theory, Encyclopedia of Mathematics and its Applications, Addison-Wesley, 1984. Zbl0554.05001 MR746795 · Zbl 0554.05001
[26] 26. K. WEILER, Edge-based Data Structures for Solid Modeling in Curved-Surface Environments, Computer Graphics and Applications, 1985, 5, n^\circ 1, p. 21-40.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.