Algebraic decomposition of non-convex polyhedra
Edelsbrunner H. 1995. Algebraic decomposition of non-convex polyhedra. Proceedings of IEEE 36th Annual Foundations of Computer Science. FOCS: Foundations of Computer Science, 248–257.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Author
Abstract
Any arbitrary polyhedron P contained as a subset within Rd 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.
Publishing Year
Date Published
1995-10-01
Proceedings Title
Proceedings of IEEE 36th Annual Foundations of Computer Science
Acknowledgement
The author thanks Bei-Fang Chen, Siu-Wing Cheng, David Dobkin, Nikolai Dolbilin, Ping Fu, Sergei Ryshkov, and Vadim Shapiro for discussions on the topic of this paper.
Page
248 - 257
Conference
FOCS: Foundations of Computer Science
Conference Location
Milwaukee, WI, United States of America
Conference Date
1995-10-23 – 1995-10-25
ISSN
IST-REx-ID
Cite this
Edelsbrunner H. Algebraic decomposition of non-convex polyhedra. In: Proceedings of IEEE 36th Annual Foundations of Computer Science. IEEE; 1995:248-257.
Edelsbrunner, H. (1995). Algebraic decomposition of non-convex polyhedra. In Proceedings of IEEE 36th Annual Foundations of Computer Science (pp. 248–257). Milwaukee, WI, United States of America: IEEE.
Edelsbrunner, Herbert. “Algebraic Decomposition of Non-Convex Polyhedra.” In Proceedings of IEEE 36th Annual Foundations of Computer Science, 248–57. IEEE, 1995.
H. Edelsbrunner, “Algebraic decomposition of non-convex polyhedra,” in Proceedings of IEEE 36th Annual Foundations of Computer Science, Milwaukee, WI, United States of America, 1995, pp. 248–257.
Edelsbrunner H. 1995. Algebraic decomposition of non-convex polyhedra. Proceedings of IEEE 36th Annual Foundations of Computer Science. FOCS: Foundations of Computer Science, 248–257.
Edelsbrunner, Herbert. “Algebraic Decomposition of Non-Convex Polyhedra.” Proceedings of IEEE 36th Annual Foundations of Computer Science, IEEE, 1995, pp. 248–57.
Link(s) to Main File(s)
Access Level
Closed Access
Google Scholar