The complexity of cutting complexes
combinatorial geometrycomputational geometryconvex subdivisionextremal functionspolynomial algorithmsthree-dimensional convex polytope
Extremal problems in graph theory (05C35) Convex sets in (2) dimensions (including convex curves) (52A10) Convex sets in (3) dimensions (including convex surfaces) (52A15) Other problems of combinatorial convexity (52A37) Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99)
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.
- 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
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 3261280 (Why is no real title available?)
- scientific article; zbMATH DE number 3311772 (Why is no real title available?)
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Research Problems in Discrete Geometry
- Topologically sweeping an arrangement
- Convex subdivisions with low stabbing numbers
- Ray shooting in polygons using geodesic triangulations
- Complexity and behind the horizon cut off
- Packing of concave polyhedra with continuous rotations using nonlinear optimisation
- Stabbing convex subdivisions with \(k\)-flats
- Complexity of projected images of convex subdivisions
- Optimized packing multidimensional hyperspheres: a unified approach
- Optimal clustering of a pair of irregular objects
- Sparsest balanced packing of irregular 3D objects in a cylindrical container
- Packing ellipsoids in an optimized cylinder
- Packing ellipses in an optimized convex polygon
- Optimized packing clusters of objects in a rectangular container
- Moser's shadow problem
- Compact representations of cuts
- Monotone paths in planar convex subdivisions and polytopes
- Quasi-phi-functions and optimal packing of ellipses
- Balance Layout Problems: Mathematical Modeling and Nonlinear Optimization
- Optimized object packings using quasi-phi-functions
- Decomposition algorithm for irregular placement problems
- Packing convex 3D objects with special geometric and balancing conditions
- Shadows of Newton polytopes
- Proportional packing of circles in a circular container
- Discrete geometry. Abstracts from the workshop held January 21--26, 2024
- The best ways to slice a polytope
- Combinatorial configurations in balance layout optimization problems
- Balance layout problem for 3D-objects: mathematical model and solution methods
- Combinatorial optimization model of packing rectangles with stochastic parameters
This page was built for publication: The complexity of cutting complexes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1115186)
