The complexity of cutting complexes
Chazelle B, Edelsbrunner H, Guibas L. 1989. The complexity of cutting complexes. Discrete & Computational Geometry. 4(1), 139–181.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Author
Chazelle, Bernard;
Edelsbrunner, HerbertISTA 
;
Guibas, Leonidas
;
Guibas, LeonidasAbstract
This paper investigates the combinatorial and computational aspects of certain extremal geometric problems in two and three dimensions. Specifically, we examine the problem of intersecting a convex subdivision with a line in order to maximize the number of intersections. A similar problem is to maximize the number of intersected facets in a cross-section of a three-dimensional convex polytope. Related problems concern maximum chains in certain families of posets defined over the regions of a convex subdivision. In most cases we are able to prove sharp bounds on the asymptotic behavior of the corresponding extremal functions. We also describe polynomial algorithms for all the problems discussed.
Publishing Year
Date Published
1989-03-01
Journal Title
Discrete & Computational Geometry
Acknowledgement
Bernard Chazelle wishes to acknowledge the National Science Foundation for supporting this research in part under Grant No. MCS83-03925. Herbert Edelsbrunner is pleased to acknowledge the support of Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862. We wish to thank J. Pach and E. Szemeredi for valuable discussions on several
of the problems studied in this paper.
Volume
4
Issue
1
Page
139 - 181
ISSN
eISSN
IST-REx-ID
Cite this
Chazelle B, Edelsbrunner H, Guibas L. The complexity of cutting complexes. Discrete & Computational Geometry. 1989;4(1):139-181. doi:10.1007/BF02187720
Chazelle, B., Edelsbrunner, H., & Guibas, L. (1989). The complexity of cutting complexes. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187720
Chazelle, Bernard, Herbert Edelsbrunner, and Leonidas Guibas. “The Complexity of Cutting Complexes.” Discrete & Computational Geometry. Springer, 1989. https://doi.org/10.1007/BF02187720.
B. Chazelle, H. Edelsbrunner, and L. Guibas, “The complexity of cutting complexes,” Discrete & Computational Geometry, vol. 4, no. 1. Springer, pp. 139–181, 1989.
Chazelle B, Edelsbrunner H, Guibas L. 1989. The complexity of cutting complexes. Discrete & Computational Geometry. 4(1), 139–181.
Chazelle, Bernard, et al. “The Complexity of Cutting Complexes.” Discrete & Computational Geometry, vol. 4, no. 1, Springer, 1989, pp. 139–81, doi:10.1007/BF02187720.
Link(s) to Main File(s)
Access Level
Closed Access
Google Scholar