The complexity of cutting complexes

DOI10.1007/BF02187720zbMath0663.68055MaRDI QIDQ1115186

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas

Publication date: 1989

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131069

zbMATH Keywords

extremal functionscombinatorial geometrypolynomial algorithmscomputational geometryconvex subdivisionthree-dimensional convex polytope

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Computing methodologies and applications (68U99) Other problems of combinatorial convexity (52A37) Convex sets in (2) dimensions (including convex curves) (52A10) Convex sets in (3) dimensions (including convex surfaces) (52A15)

Related Items

Ray shooting in polygons using geodesic triangulations, Quasi-phi-functions and optimal packing of ellipses, Packing ellipsoids in an optimized cylinder, Shadows of Newton polytopes, Proportional packing of circles in a circular container, Decomposition Algorithm for Irregular Placement Problems, Packing Convex 3D Objects with Special Geometric and Balancing Conditions, Optimized Object Packings Using Quasi-Phi-Functions, Optimized packing multidimensional hyperspheres: a unified approach, Packing of concave polyhedra with continuous rotations using nonlinear optimisation, Optimal clustering of a pair of irregular objects, Packing ellipses in an optimized convex polygon, Combinatorial configurations in balance layout optimization problems, Sparsest balanced packing of irregular 3D objects in a cylindrical container, Stabbing convex subdivisions with \(k\)-flats, Optimized packing clusters of objects in a rectangular container, Balance layout problem for 3D-objects: mathematical model and solution methods, Combinatorial optimization model of packing rectangles with stochastic parameters, Moser's shadow problem, Convex subdivisions with low stabbing numbers, Monotone Paths in Planar Convex Subdivisions and Polytopes, Balance Layout Problems: Mathematical Modeling and Nonlinear Optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Topologically sweeping an arrangement
• Research Problems in Discrete Geometry
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• A convex 3-complex not simplicially isomorphic to a strictly convex complex
• Facing up to arrangements: face-count formulas for partitions of space by hyperplanes