scientific article

zbMath0487.68033MaRDI QIDQ3948588

Andrzej Lingas

Publication date: 1982

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

computational geometryNP-hard problemsgeometric complexityrectilinear polygonspolygonal holesmulticonnected polygons

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Combinatorial aspects of packing and covering (05B40)

Related Items

Convex polygons made from few lines and convex decompositions of polyhedra ⋮ Convex Partitions with 2-Edge Connected Dual Graphs ⋮ Erased arrangements of linear and convex decompositions of polyhedra ⋮ SFCDecomp: Multicriteria Optimized Tool Path Planning in 3D Printing using Space-Filling Curve Based Domain Decomposition ⋮ Rectangularization of digital objects and its relation with straight skeletons ⋮ Minimum k-partitioning of rectilinear polygons ⋮ Triangulating a nonconvex polytope ⋮ Convex partitions with 2-edge connected dual graphs ⋮ Algorithms for the decomposition of a polygon into convex polygons ⋮ Decomposing the boundary of a nonconvex polyhedron ⋮ Minimum dissection of a rectilinear polygon with arbitrary holes into rectangles ⋮ Some theoretical challenges in digital geometry: a perspective ⋮ Decomposing the boundary of a nonconvex polyhedron ⋮ Minimum weight convex Steiner partitions ⋮ Approximate convex decomposition of polygons ⋮ A fixed parameter algorithm for optimal convex partitions ⋮ On the minimality of polygon triangulation ⋮ Digitization scheme that assures faithful reconstruction of plane figures ⋮ On convex partitions of polygonal regions ⋮ A decision procedure for optimal polyhedron partitioning ⋮ Rectangular partition is polynomial in two dimensions but NP-complete in three