The complexity of cutting complexes
type: Item
instance of: scholarly article
title: The complexity of cutting complexes
zbMATH Open document ID: 0663.68055
DOI: 10.1007/BF02187720
author: Bernard Chazelle
author: Herbert Edelsbrunner
author: Leonidas Guibas
published in: Discrete \& Computational Geometry
publication date: 1989-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/131069
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68U99
Mathematics Subject Classification ID: 52A37
Mathematics Subject Classification ID: 52A10
Mathematics Subject Classification ID: 52A15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4085022
zbMATH Keywords: computational geometry
zbMATH Keywords: combinatorial geometry
zbMATH Keywords: convex subdivision
zbMATH Keywords: three-dimensional convex polytope
zbMATH Keywords: extremal functions
zbMATH Keywords: polynomial algorithms
MaRDI profile type: Publication
cites work: A convex 3-complex not simplicially isomorphic to a strictly convex complex
cites work: Q3772828
cites work: Topologically sweeping an arrangement
cites work: Q5547252
cites work: Primitives for the manipulation of general subdivisions and the computation of Voronoi
cites work: Q5592263
cites work: Research Problems in Discrete Geometry
cites work: Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
description: scientific article; zbMATH DE number 4085022