Improved bounds on the union complexity of fat objects

DOI10.1007/S00454-007-9029-7MaRDI QIDQ946687zbMATH OpenOpenAlexFDO

Authors Mark de Berg

Publication date 24 September 2008

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

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

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)

Recommendations

• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Improved bounds for the union of locally fat objects in the plane
• Better bounds on the union complexity of locally fat objects
• On the complexity of the union of fat convex objects in the plane
• The Complexity of the Union of $(\alpha,\beta)$-Covered Objects

Cites work

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

Cited in

(20)

• A note about weak \(\epsilon \)-nets for axis-parallel boxes in \(d\)-space
• The Complexity of the Union of $(\alpha,\beta)$-Covered Objects
• Approximation algorithms for polynomial-expansion and low-density graphs
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• On the complexity of barrier resilience for fat regions and bounded ply
• On the union complexity of families of axis-parallel rectangles with a low packing number
• Decomposition of Multiple Packings with Subquadratic Union Complexity
• Unions of fat convex polytopes have short skeletons
• On the union of cylinders in three dimensions
• A note on the perimeter of fat objects
• Approximating the Fréchet distance for realistic curves in near linear time
• State of the union (of geometric objects)
• Computing the visibility map of fat objects
• scientific article; zbMATH DE number 1786523 (Why is no real title available?)
• Better bounds on the union complexity of locally fat objects
• Decompositions and boundary coverings of non-convex fat polyhedra
• Improved bounds for the union of locally fat objects in the plane
• On the complexity of the union of fat convex objects in the plane
• The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains
• Jaywalking your dog: computing the Fréchet distance with shortcuts

This page was built for publication: Improved bounds on the union complexity of fat objects

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q946687)