Improved Bounds for the Union of Locally Fat Objects in the Plane

DOI10.1137/120891241zbMath1295.05258OpenAlexW2140049544MaRDI QIDQ5494929

Esther Ezra, Boris Aronov, Mark T. de Berg, Micha Sharir

Publication date: 30 July 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://research.tue.nl/nl/publications/improved-bounds-for-the-union-of-locally-fat-objects-in-the-plane(4e9fc0a1-310f-4e61-bc56-979395b4eabf).html

zbMATH Keywords

combinatorial geometryunion complexityfat objects

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Extremal combinatorics (05D99) Combinatorial complexity of geometric structures (52C45)

Related Items (16)

Dynamic conflict-free colorings in the plane ⋮ Finding Pairwise Intersections Inside a Query Range ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning ⋮ Geometric Packing under Nonuniform Constraints ⋮ Clique-based separators for geometric intersection graphs ⋮ Near-linear approximation algorithms for geometric hitting sets ⋮ Approximating the k-Level in Three-Dimensional Plane Arrangements ⋮ Unions of fat convex polytopes have short skeletons ⋮ Finding pairwise intersections inside a query range ⋮ Near-linear algorithms for geometric hitting sets and set covers ⋮ Parameterized complexity of geometric covering problems having conflicts ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ Dynamic Conflict-Free Colorings in the Plane ⋮ Stochastic makespan minimization in structured set systems

This page was built for publication: Improved Bounds for the Union of Locally Fat Objects in the Plane