The number of holes in the union of translates of a convex set in three dimensions

DOI10.1007/s00454-016-9820-4zbMath1361.52005OpenAlexW3105232823MaRDI QIDQ512258

Michael Gene Dobbins, Xavier Goaoc, Boris Aronov, Otfried Schwarzkopf

Publication date: 24 February 2017

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

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5902/

zbMATH Keywords

convex setsmotion planningunion complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Convex sets in (3) dimensions (including convex surfaces) (52A15)

Uses Software

• Voronoi

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Union of random Minkowski sums and network vulnerability analysis
• Improved approximation algorithms for geometric set cover
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Polyhedral Voronoi diagrams of polyhedra in three dimensions
• On the complexity of the union of fat convex objects in the plane
• On the Boundary Complexity of the Union of Fat Triangles
• On Translational Motion Planning of a Convex Polyhedron in 3-Space
• On the imbedding of systems of compacta in simplicial complexes