Algebraic decomposition of non-convex polyhedra
- 19 November 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Any arbitrary polyhedron P/spl sube/R/sup d/ can be written as algebraic sum of simple terms, each an integer multiple of the intersection of d or fewer half-spaces defined by facets of P. P can be non-convex and can have holes of any kind. Among the consequences of this result are a short boolean formula for P, a fast parallel algorithm for point classification, and a new proof of the Gram-Sommerville angle relation.Keywords
This publication has 16 references indexed in Scilit:
- The Incidence Algebra of Polyhedra over the Minkowski AlgebraAdvances in Mathematics, 1996
- An efficient algorithm for finding the CSG representation of a simple polygonAlgorithmica, 1993
- The union of balls and its dual shapePublished by Association for Computing Machinery (ACM) ,1993
- Inclusion-Exclusion-Bonferroni Identities and Inequalities for Discrete Tube-Like Problems via Euler CharacteristicsThe Annals of Statistics, 1992
- The Gram-Sommerville and Gauss-Bonnet theorems and combinatorial geometric measures for noncompact polyhedraAdvances in Mathematics, 1992
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithmsACM Transactions on Graphics, 1990
- Algorithms in Combinatorial GeometryPublished by Springer Nature ,1987
- A symbolic method for calculating the integral properties of arbitrary nonconvex polyhedraIEEE Computer Graphics and Applications, 1984
- A kinetic framework for computational geometryPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Vorlesungen Über Inhalt, Oberfläche und IsoperimetriePublished by Springer Nature ,1957