Subdivisions of n-dimensional spaces and n-dimensional generalized maps

ABSTRACT

This paper deals with the modeling of n-dimensional objects, more precisely with the modeling of subdivisions of n-dimensional topological spaces. We here study the notions of: n-dimensional generalized map (or n-G-map), for the modeling of the topology of any subdivision of any n-dimensional topological space (orientable or not orientable, with or without boundaries); n-dimensional map (or n-map), for the modeling of the topology of any subdivision of any orientable n-dimensional topological space, without boundaries. These two notions extend the notion of topological map, which has been used for the modeling of the topology of any subdivision of any surface. We study in this paper some properties of the n-G-maps and the n-maps (orientability, duality, relationships between n-G-maps and n-maps …), and we define also operations for constructing any n-G-map.

REFERENCES

• 1: B. Baumgart : A Polyhedron Representation for Computer Vision . AFIPS Nat. Conf. Proc. Vol. 44, 1975, pp. 589-596 .
• 2: C. Berge : Graphes et hypergraphes . Dunod, Paris, 1970 .
• 3: R. Cori : Un co& pour les graphes planaires et ses applications. Ast&isque no 27,1975 .
• 4: D. P. Dobkin , M. J. Laszlo, Primitives for the manipulation of three-dimensional subdivisions, Proceedings of the third annual symposium on Computational geometry, p.86-99, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41967]
• 5: J.-F. Dufourd : Spe'ctfication Progressive dune Algebre pour Manipuler les Cartes Topologiques orientees . Pixim'88, Paris, Hermes, pp. 61-80, 1988 .
• 6: J.-F. Dufourd, C. Gross, J.-C. Spehner : A Digitisation Algorithm for the Entry of Planar Maps . Computer Graphics International'89, Leeds, Springer-Verlag, 1989 .
• 7: J.-F. Dufourd : A Topological Map-based Kernel for Polyhedron Modellers : Algebraic Specification and Logic Prototyping . Eurographics'89, Hamburg, Elsevier, 1989 .
• 8: J. Edmonds : A Combinatorial Representation for Polyhedral Sut$aces . Notices Amer. Math. Sot. no 7, 1960 .
• 9: H. B. Griffiths : Surfaces . Cambridge University Press, Cambridge, 2" edition, 1981 .
• 10: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 11: : A. Jacques : Constellations et Graphes Topologiques . Colloque Math. Sot. Janos Bolyai, North-Holland, 1970, pp. 657672 .
• 12: L. James : Maps and Hypermaps : Operations and Symmetry. PhD thesis, Department of Mathematics, University of Southampton, U.K., August 1985.
• 13: Pascal Lienhardt, Extension of the Notion of Map and Subdivisions of a Three-Dimensional Space, Proceedings of the 5th Annual Symposium on Theoretical Aspects of Computer Science, p.301-311, February 11-13, 1988
• 14: P. Lienhardt : Subdivisions de surfaces, cartes et S-V-cartes. Research Report RSS-4, Departement d'Informatique, Universite Louis Pasteur, Strasbourg, France (submitted to R.A.I.R.O. Informatique Theorique et Applications) .
• 15: P. Lienhardt : Subdivisions of surfaces and generalized maps . Research Report R88-11, Departement d'Informatique, Universite Louis Pasteur, Strasbourg, France (accepted at EurographicsB9) .
• 16: P. Lienhardt : N-dimensional Generalized Maps . Research Report R89-04, Departement d'Informatique, Universitt Louis Pasteur, Strasbourg, France .
• 17: M. Mantyll : Computational Topology : a Study of Topological Manipulations and Interrogations in Computer Graphics and Geometric Modeling . Acta Polytechnica Scandinavia, no 37, 1983, Helsinski .
• 18: L. K. Putnam , P. A. Subrahmanyam, Boolean operations on n-dimensional objects, IEEE Computer Graphics and Applications, v.6 n.6, p.43-51, June 1986 [doi>10.1109/MCG.1986.276741]
• 19: Aristides G. Requicha, Representations for Rigid Solids: Theory, Methods, and Systems, ACM Computing Surveys (CSUR), v.12 n.4, p.437-464, Dec. 1980 [doi>10.1145/356827.356833]
• 20: H. Seifert and W. Threlfall : Lehrbuch der Topologie . Chelsea, New York, 1947 .
• 21: W. Tutte : Graph Theory . Encyclopedia of Mathematics and its Applications, Addison-Wesley, 1984 .
• 22: K. Weiler : Edge-based Data Structures for Solid Modeling in Curved-Surface Environments . Computer Graphics and Applications, Vol. 5, no 1, 1985, pp. 21-40.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Theory