Author(s): | Edelsbrunner, Herbert |
Title: | Algebraic decomposition of non-convex polyhedra |
Affiliation | |
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. |
Keywords: | Computer Simulation; data structures; computational complexity; Computer science; Parallel algorithms |
Conference Title: | FOCS: Foundations of Computer Science |
Conference Dates: | October 23-25, 1995 |
Conference Location: | Milwaukee, WI, USA |
Publisher: | IEEE |
Location: | Washington, DC, USA |
Date Published: | 1995-10-01 |
Start Page: | 248 |
End Page: | 257 |
Open access: | no |