The complexity of cutting complexes

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas

Research output: Contribution to journalArticle

33 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)139-181
Number of pages43
JournalDiscrete & Computational Geometry
Volume4
Issue number1
DOIs
StatePublished - Dec 1 1989

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'The complexity of cutting complexes'. Together they form a unique fingerprint.

  • Cite this