Algebraic decomposition of non-convex polyhedra Conference Paper


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
IST Austria Authors
Related IST Austria Work