Abstract
We present an algorithm EULER for the computation of the Euler-characteristic χ(P) of bounded polyhedraP⊂ℝd. It is first shown that χ(P) is uniquely determined by the local properties ofP at its vertices. It is therefore possible to compute χ(P) using a plane sweeping through ℝd, collecting the local information available at every vertex. There is a close relationship with an algorithm for the computation of the volumeV (P) published earlier (cf. [4]). The reason is that both ofV and χ are additive functionals.
Zusammenfassung
Wir präsentieren einen Algorithmus EULER für die Berechnung der Eulerschen Charakteristik χ(P) beschränkter PolyederP⊂ℝd. Es wird gezeigt, daß χ(P) durch die lokalen Eigenschaften vonP in seinen Ecken eindeuting bestimmt ist. Deshalb ist es möglich, χ(P) mit Hilfe einer Ebene zu berechnen, die durch den Raum gleitet („sweep-plane”) und die in den Ecken verfügbare Information „sammelt”. Es besteht eine enge Beziehung zu einem früher publizierten Algorithmus für die Berechnung des VolumensV (P) (vgl. [4]). Der Grund liegt darin, daßV und χ beide additive Funktionale sind.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alexanderson, G. L., Wetzel, J. E.: Simple partitions of space. Math. Mag.51, 220–225 (1978).
Bentley, J. L., Ottmann, T. A.: Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput.C-28, 643–647 (1979).
Bieri, H., Nef, W.: A recursive sweep-plane algorithm, determining all cells of a finite division of ℝd. Computing28, 189–198 (1982).
Bieri, H., Nef, W.: A sweep-plane algorithm for computing the volume of polyhedra represented in Boolean form. Linear Algebra Appl.52/53, 69–97 (1983).
Brousseau, Bro. A.: A mathematician's progress. Math. Teacher59, 722–727 (1966).
Groemer, H.: Eulersche Charakteristik, Projektionen und Quermaßintegrale. Math. Ann.198, 23–56 (1972).
Groemer, H.: Über einige Invarianzeigenschaften der Eulerschen Charakteristik. Comment. Math. Helv.48, 87–99 (1973).
Groemer, H.: On the Euler characteristic in spaces with a separability property. Math. Ann.211, 315–321 (1974).
Groemer, H.: The Euler characteristic and related functionals on convex surfaces. Geometriae Dedicata4, 91–104 (1975).
Groemer, H.: On the extension of additive functionals on classes of convex sets. Pacific J. Math.75, 397–410 (1978).
Hadwiger, H.: Eulers Charakteristik und kombinatorische Goemetrie. J. reine angew. Math.194, 101–110 (1955).
Hadwiger, H.: Eine Schnittrekursion für die Eulersche Charakteristik euklidischer Polyeder mit Anwendungen innerhalb der kombinatorischen Geometrie. Elem. Math.23, 121–132 (1968).
Hadwiger, H.: Notiz zur Eulerschen Charakteristik offener und abgeschlossener Euklidischer Polyeder. Studia Sci. Math. Hung.4, 385–387 (1969).
Hadwiger, H.: Erweiterter Polyedersatz und Euler-Sherapardsche Additionstheoreme. Abh. Math. Seminar Univ. Hamburg39, 120–129 (1973).
Hadwiger, H., Mani, P.: On the Euler characteristic of spherical polyhedra and the Euler relation. Mathematika19, 139–143 (1972).
Hadwiger, H., Mani, P.: On polyhedra with extremal Euler characteristic. J. Comb. TheoryA 17, 345–349 (1974).
Kerr, J. W., Wetzel, J. E.: Platonic divisions of space. Math. Mag.51, 229–234 (1978).
Klee, V.: The Euler characteristic in combinatorial geometry. Am. Math. Monthly70, 119–127 (1963).
Lenz, H.: Mengenalgebra und Eulersche Charakteristik. Abh. Math. Seminar Univ. Hamburg34, 135–147 (1970).
Nef, W.: Zur Eulerschen Charakteristik allgemeiner, insbesondere konvexer Polyeder. Resultate Math.3, 64–69 (1980).
Nef, W.: Beiträge zur Theorie der Polyeder, mit Anwendungen in der Computergraphik. Bern: Herbert Lang 1978.
Nef, W.: Zur Einführung der Eulerschen Charakteristik. Monatsch. Math.92, 41–46 (1981).
Nef, W.: Ein einfacher Beweis des Satzes von Euler-Schlaefli. Elem. Math.39, 1–6 (1984).
Nievergelt, J., Preparata, F. P.: Plane-sweep algorithms for intersecting geometric figures. Comm. ACM25, 739–747 (1982).
Shamos, M. I., Hoey, D.: Geometric intersection problems. 17th Annual IEEE Symp. Foundations of Comput. Sci.1976, 208–215.
Shamos, M. I.: Computational Geometry. Ph. D. Thesis, Yale University, 1978. Ann Arbor: University Microfilms International.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bieri, H., Nef, W. A sweep-plane algorithm for computing the Euler-characteristic of polyhedra represented in Boolean form. Computing 34, 287–302 (1985). https://doi.org/10.1007/BF02251831
Received:
Issue date:
DOI: https://doi.org/10.1007/BF02251831