Improved bounds on the union complexity of fat objects

DOI10.1007/s00454-007-9029-7zbMath1158.68048OpenAlexW2170429689MaRDI QIDQ946687

Mark T. de Berg

Publication date: 24 September 2008

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

Full work available at URL: https://doi.org/10.1007/s00454-007-9029-7

zbMATH Keywords

union complexityfat objectsdensity lemma

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial complexity of geometric structures (52C45)

Related Items

On the complexity of barrier resilience for fat regions and bounded ply ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ A note about weak \(\epsilon \)-nets for axis-parallel boxes in \(d\)-space ⋮ On the union of cylinders in three dimensions ⋮ Decomposition of Multiple Packings with Subquadratic Union Complexity ⋮ Approximating the Fréchet distance for realistic curves in near linear time ⋮ Unions of fat convex polytopes have short skeletons ⋮ The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains ⋮ A note on the perimeter of fat objects ⋮ Computing the visibility map of fat objects ⋮ Decompositions and boundary coverings of non-convex fat polyhedra ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• On the union of \(\kappa\)-round objects in three and four dimensions
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
• Efficient hidden surface removal for objects with small union size
• On the union of fat wedges and separating a collection of segments by a line
• The complexity of the free space for a robot moving amidst fat obstacles
• 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects
• On fat partitioning, fat covering and the union size of polygons
• The union of congruent cubes in three dimensions
• The complexity of the free space for motion planning amidst fat obstacles
• Sharp quantum versus classical query complexity separations
• Computing depth orders for fat objects and related problems
• On the Boundary Complexity of the Union of Fat Triangles
• Vertical ray shooting and computing depth orders for fat objects
• Fat Triangles Determine Linearly Many Holes
• The Complexity of the Union of $(\alpha,\beta)$-Covered Objects
• Vertical ray shooting for fat objects