---
_id: '4034'
abstract:
- lang: eng
text: 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.
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.
article_processing_charge: No
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: 'Edelsbrunner H. Algebraic decomposition of non-convex polyhedra. In: *Proceedings
of IEEE 36th Annual Foundations of Computer Science*. IEEE; 1995:248-257.'
apa: '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.'
chicago: Edelsbrunner, Herbert. “Algebraic Decomposition of Non-Convex Polyhedra.”
In *Proceedings of IEEE 36th Annual Foundations of Computer Science*, 248–57.
IEEE, 1995.
ieee: 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.
ista: '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.'
mla: Edelsbrunner, Herbert. “Algebraic Decomposition of Non-Convex Polyhedra.” *Proceedings
of IEEE 36th Annual Foundations of Computer Science*, IEEE, 1995, pp. 248–57.
short: H. Edelsbrunner, in:, Proceedings of IEEE 36th Annual Foundations of Computer
Science, IEEE, 1995, pp. 248–257.
conference:
end_date: 1995-10-25
location: Milwaukee, WI, United States of America
name: 'FOCS: Foundations of Computer Science'
start_date: 1995-10-23
date_created: 2018-12-11T12:06:33Z
date_published: 1995-10-01T00:00:00Z
date_updated: 2022-06-13T12:27:11Z
day: '01'
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://ieeexplore.ieee.org/abstract/document/492480
month: '10'
oa_version: None
page: 248 - 257
publication: Proceedings of IEEE 36th Annual Foundations of Computer Science
publication_identifier:
issn:
- 0272-5428
publication_status: published
publisher: IEEE
publist_id: '2093'
quality_controlled: '1'
status: public
title: Algebraic decomposition of non-convex polyhedra
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1995'
...