Computing Covers of Plane Forests

Abstract

Let $\varphi$ be a function that maps any non-empty subset $A$ of ${\mathbb{R}}^2$ to a non-empty subset $\varphi (A)$ of ${\mathbb{R}}^2$. A $\varphi$-cover of a set $T=\{T_1,T_2,\dots ,T_m\}$ of pairwise non-crossing trees in the plane is a set of pairwise disjoint connected regions such that each tree $T_i$ is contained in some region of the cover, and each region of the cover is either (1) $\varphi (T_i)$ for some $i$, or (2) $\varphi (A\cup B)$, where $A$ and $B$ are constructed by either (1) or (2), and $A\cap B\ne \varnothing$. We present two properties for the function $\varphi$ that make the $\varphi$-cover well-defined. Examples for such functions $\varphi$ are the convex hull and the axis-aligned bounding box. For both of these functions $\varphi$, we show that the $\varphi$-cover can be computed in $O(n{\log }^{2}n)$ time, where $n$ is the total number of vertices of the trees in $T$.

6 pages, 3 figures. Accepted and presented at the 25th annual Canadian Conference on Computational Geometry (CCCG 2013)

References in corpus (1)

• Computing the Coverage of an Opaque Forest

Cited by in corpus (1)

• Covering Polygons by Min-Area Convex Polygons