The complexity of cutting complexes
Copyright policy )The complexity of cutting complexes
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.
- College of New Jersey United States
- University of Illinois System United States
- DigiZeitschriften Germany
- Stanford University United States
- University of Illinois at Urbana Champaign United States
Extremal problems in graph theory, polynomial algorithms, Computing methodologies and applications, convex subdivision, Analysis of algorithms and problem complexity, Other problems of combinatorial convexity, three-dimensional convex polytope, Convex sets in \(2\) dimensions (including convex curves), Article, extremal functions, 510.mathematics, computational geometry, combinatorial geometry, Convex sets in \(3\) dimensions (including convex surfaces)
Extremal problems in graph theory, polynomial algorithms, Computing methodologies and applications, convex subdivision, Analysis of algorithms and problem complexity, Other problems of combinatorial convexity, three-dimensional convex polytope, Convex sets in \(2\) dimensions (including convex curves), Article, extremal functions, 510.mathematics, computational geometry, combinatorial geometry, Convex sets in \(3\) dimensions (including convex surfaces)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).43 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!