The Complexity of the Union of (\alpha,\beta)-Covered Objects
The author introduces a new class of `fat' nonconvex objects, called \((\alpha,\beta)\)-covered objects, and obtains sharp bounds for the maximum combinatorial complexity of unions of such objects. An \((\alpha,\beta)\)-covered object is defined as a compact simply connected planar set \(c\) having the property that for each point \(p\in\partial c\) there exists a triangle contained in \(c\) with \(p\) as a vertex, such that all its angles are at least \(\alpha\) and all its edges are at least \(\beta\cdot\)diam\((c)\). Assuming that \(n\) \((\alpha,\beta)\)-covered objects are in general position and have `constant description complexity', it is proved that the combinatorial complexity of their union is \[ O(\lambda_{s+2}(n)\log^2 n\log\log n), \] where \(s\) is the maximum number of intersections between the boundaries of any pair of given objects, and \(\lambda_{s}(n)\) denotes the maximum length of an \((n,s)\)-Davenport-Schinzel sequence. This result extends and improves previous results on convex \(\alpha\)-fat objects.
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Improved bounds on the union complexity of fat objects
- On the complexity of the union of fat convex objects in the plane
- Improved bounds for the union of locally fat objects in the plane
- Better bounds on the union complexity of locally fat objects
- Decompositions and boundary coverings of non-convex fat polyhedra
- On the complexity of barrier resilience for fat regions and bounded ply
- On the union of \(\kappa\)-curved objects
- On the complexity of the union of fat convex objects in the plane
- Connect the Dot: Computing Feed-Links with Minimum Dilation
- A note about weak -nets for axis-parallel boxes in d-space
- Tangencies between families of disjoint regions in the plane
- Approximating the Fréchet distance for realistic curves in near linear time
- Decomposition of Multiple Packings with Subquadratic Union Complexity
- Better bounds on the union complexity of locally fat objects
- Jaywalking your dog: computing the Fréchet distance with shortcuts
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- On the union of cylinders in three dimensions
- Robustly guarding polygons
- A note on the perimeter of fat objects
- On realistic terrains
- Improved bounds on the union complexity of fat objects
This page was built for publication: The Complexity of the Union of $(\alpha,\beta)$-Covered Objects
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5317174)
