Merging in maps and in pavings. (English) Zbl 0733.68093

The author introduces the notion of paving, which gives a method for defining data structures for modeling a solid. Pavings allow an easy definition of incidence relations between vertices, edges, faces and pieces. The notion of paving is a generalization of the notion of map, which is directly associated to a subdivision of \({\mathcal E}^ 3\). After generalities on pavings the paper deals with merging in maps and merging in pavings. A fundamental relation between the characteristic of a paving and the genus of the underlying map is proved.
Reviewer: H.-D.Hecker (Jena)


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI


[1] Ansaldi, S.; de Floriani, L.; Falcidieno, B., Geometric modelling of solid objects by using graph representation, Proc. SIGGRAPH’85 ACM, 131-139 (1985), San Francisco
[2] Arquès, D.; Koch, P., Définition et implémentation de pavages dans l’espace, Theoret. Comput. Sci., 77, 331-343 (1990)
[3] Baumgart, B. G., A polyhedron representation for computer vision, AFIPS Nat. Comput. Conf., 44, 589-596 (1975)
[4] Brisson, E., Representing geometric structures in \(d\) dimensions: topology and order, Proc. 5th Ann. ACM Symp. on Computational Geometry, 212-227 (1989)
[5] Cori, R., Un code pour les graphes planaires et ses applications, Asterisque, 27 (1975) · Zbl 0313.05115
[6] Dobkin, D. P.; Laszlo, M. J., Primitives for the manipulation of three-dimensional subdivisions, Algorithmica, 4, 3-32 (1989) · Zbl 0664.68023
[7] Dufourd, J. F., A topological map-based kernel for polyhedron modelers: Algebraic specification and logic prototyping, Proc. Eurographics ’89, 301-312 (1989)
[8] Elbaz, M.; Spehner, J. C., Construction of Voronoi diagrams in the plane by using maps, Theoret. Comput. Sci., 77, 331-343 (1990) · Zbl 0715.68085
[9] Euler, L., Elementa doctrinae solidorum, Novi. Comm. Acad. Sci. Imp. Petropol., 4, 109-140 (1752-1753)
[10] Fontet, M., Connectivité des graphes et automorphismes des cartes: propriétés et algorithmesv, 7 (1979), Thèse Université de Paris
[11] Guibas, L.; Stolfi, J., Primitives for the manipulation of general subdivision and the computation of Voronoi diagrams, ACM Trans. Graphics, 4, 2, 74-123 (1985) · Zbl 0586.68059
[12] Jacques, A., Sur le genre d’une paire de substitutions, Série A, 267, 625-627 (1968) · Zbl 0187.20902
[13] Lienhardt, P., Extension of the notion of map and subdivision of the three-dimensional space, Proc. STACS’88, Vol. 294, 301-311 (1988), Lecture Notes in Computer Science · Zbl 0654.05026
[14] Lienhardt, P., Subdivision de surfaces, cartes et S-V-cartes (1988), U.L.P. Strasbourg, Public. No. 4
[15] Lienhardt, P., Subdivisions of \(n\)-dimensional spaces and \(n\)-dimensional generalized maps, Proc. 5th Ann. ACM Symp. on Computational Geometry, 228-236 (1989)
[16] Mäntylä, M.; Sulonen, R., GWB: A solid modeler with Euler operators, CG&A, 2, 7 (1982)
[17] Requicha, A., Representation for rigid solids: theory, methods and systems, Computing Surveys, 12, 4, 437-464 (1980)
[18] Schäffi, L., Theorie der vielfachen Kontinuität, Denkschr. Schweiz Natur. Ges., 38, 1-237 (1901)
[19] Spehner, J. C., On solid pavings (1988), University of Haute Alsace, Public. Math-Inform. No. 49
[20] Tutte, W. T., Graph Theory (1984), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0554.05001
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.